不是计算机相关专业毕业的,从来没用过leetcode,最近在学习数据结构和算法,用leetcode练练手。
新手上路,代码如有不妥之处,尽管指出来。
今天抽空做的第一个题:two sum(最简单的呃呃呃)
题目如下:
解决思路:
现有数组nums[p-r],首先将nums从小至大排序,然后将nums[p] + nums[r]与指定值k比较,如果nums[p] + nums[r] > k则说明nums[r]大了,r--;
反之p++,直到nums[p] + nums[r] = k。
以下是我的java实现(老实说,时间复杂度较高)
1 class solution { 2 public int[] twosum(int[] nums, int target) { 3 int[] copynums = new int[nums.length]; 4 for(int i = 0; i < nums.length; ++i){ 5 copynums[i] = nums[i]; 6 } 7 int[] result = new int[2]; 8 9 // 先排序 10 quicksort(nums, 0, nums.length - 1); 11 12 // 将两个元素之和与target相比较 13 int[] temp = compare(nums, 0, nums.length - 1, target); 14 15 boolean flaga = false; 16 boolean flagb = false; 17 for(int i = 0; i < copynums.length; ++i){ 18 if(temp[0] == copynums[i] && !flaga){ 19 result[0] = i; 20 flaga = true; 21 continue; 22 } 23 if(temp[1] == copynums[i] && !flagb){ 24 result[1] = i; 25 flagb = true; 26 } 27 } 28 return result; 29 } 30 31 private int[] compare(int[] nums, int p, int r, int target){ 32 while(p < r){ 33 int k = nums[p] + nums[r]; 34 if(k == target) 35 return new int[]{nums[p], nums[r]}; 36 if(k > target){ 37 r--; 38 }else{ 39 p++; 40 } 41 } 42 return null; 43 } 44 45 private void quicksort(int[] nums, int p, int r){ 46 if(p >= r) 47 return; 48 int q = partition(nums, p, r); 49 quicksort(nums, p, q-1); 50 quicksort(nums, q+1, r); 51 } 52 53 private int partition(int[] nums, int p, int r){ 54 // 最简单的,选择nums最后一个元素作为中间数 55 int k = nums[r]; 56 int i = p; 57 58 for(int j = p; j <= r; j++){ 59 if(nums[j] < k){ 60 int temp = nums[i]; 61 nums[i] = nums[j]; 62 nums[j] = temp; 63 ++i; 64 } 65 } 66 67 nums[r] = nums[i]; 68 nums[i] = k; 69 70 return i; 71 } 72 }
如对本文有疑问, 点击进行留言回复!!
unity的错误解决办法:NullReferenceException: Object reference not set to an instance of an object;tiny proje
Hadoop 之 HDFS (HDFS 数据流的 读写 流程)
听说你一读Spring源码就懵逼?我帮你把架子搭好了,你填就行!
首席架构师推荐:金融保险领域数字化转型实践--如何优雅地修改业务中台中分层应用Maven多模块的版本号?(命令导入式)
[JVM学习之路]一、初识JVM,了解其结构、模型及生命周期
网友评论