3Sum Closest

发布时间:2016-12-6 22:16:34 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"3Sum Closest",主要涉及到3Sum Closest方面的内容,对于3Sum Closest感兴趣的同学可以参考一下。

与3Sum问题思路相同。先排序,再固定一个值,设置左右指针,两边夹。 要找的是最接近的,如果找到了这个数,则直接返回这个数; 如果没有找到这个数,设置一个记忆值,记忆差值,如果新的差值比原来的小,则替换返回值和记忆值。 算法复杂度:O(nlogn)+O(n2)=O(n2) public int threeSumClosest(int[] num, int target) { int length = num.length; quickSort(num,0,length-1); int ret = 0; boolean isFound = false; int cha = Integer.MAX_VALUE; for(int i = 0;i<length;i++){ int t = target-num[i]; int low = i+1; int high = length-1; while(low < high){ int add = num[low]+num[high]; if(add == t){ ret = target; isFound = true; break; }else if(add < t){ if(cha > Math.abs(add-t)){ ret = add+num[i]; cha = Math.abs(add-t); } low++; }else{ if(cha > Math.abs(add-t)){ ret = add+num[i]; cha = Math.abs(add-t); } high--; } } if(isFound)break; } return ret; } void quickSort(int[] num,int left,int right){ if(left < right){ int part = partition(num,left,right); quickSort(num,left,part-1); quickSort(num,part+1,right); } } int partition(int[] num,int left,int right){ int privot = meadian3(num,left,right); int low = left+1; int high = right-1; while(true){ while(num[low]<=privot && low<high)low++; while(num[high]>privot)high--; if(low < high){ swap(num,low,high); }else{ break; } } swap(num,left,high); return high; } int meadian3(int[] num,int left,int right){ int middle = (left+right)/2; if(num[left] > num[middle]){ swap(num,left,middle); } if(num[left] > num[right]){ swap(num,left,right); } if(num[middle] > num[right]){ swap(num,middle,right); } swap(num,left,middle); return num[left]; } void swap(int[] num,int i,int j){ int temp = num[i]; num[i] = num[j]; num[j] = temp; }

上一篇:专有名词_ATL
下一篇:浅谈C中的malloc和free释放

相关文章

关键词: 3Sum Closest

相关评论