寻找两个正序数组的中位数
解法一
暴力
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int left = -1; int right = -1; int start1 = 0; int start2 = 0; for(int i = 0;i <= (m+n)/2;i++){ left = right; if(start1 < m && (start2 >= n || nums1[start1] < nums2[start2])){ right = nums1[start1++]; }else{ right = nums2[start2++]; } } if((m+n) % 2 == 0)return ((double)left+right)/2; else return right; } }
搜索旋转排序数组
解法一
二分
class Solution { public int search(int[] nums, int target) { int n = nums.length; int left = 0,right = n-1; //数组 [a1,a2...an,b1,b2...bn] 其中b1~bn小于a1 while(left <= right){ int mid = (left+right)/2; if(nums[mid] == target) return mid; if(nums[mid] >= nums[0]){ //说明mid在[a1,a2...an]区间 if(target > nums[mid]){ //说明target在[mid,...an区间] left = mid+1; }else if(target < nums[mid]){ //说明target在[a1,...mid]区间 或者在[b1,b2..bn]区间 if(target >= nums[0]){ //说明在[a1...mid]区间 right = mid -1; }else{ left = mid + 1; } } }else{ //说明mid在[b1,b2...bn]区间 if(target < nums[mid]){// 说明target在[b1,b2...mid] right = mid -1; }else{ //说明target在[mid...bn] 或者[a1...an]区间 if(target > nums[n-1]){ //说明target在[a1..an]区间 right = mid -1; }else{ //说明在[mid...bn]区间 left = mid + 1; } } } } return -1; } }
在排序数组中查找元素的第一个和最后一个位置
class Solution { public int[] searchRange(int[] nums, int target) { if(nums.length == 0) return new int[]{-1,-1}; int left = lowBinarySearch(nums,target); int right = upBinarySearch(nums,target); return new int[]{left,right}; } public int lowBinarySearch(int[] nums,int target){ int left = 0; int right = nums.length-1; while(left < right){ int mid = left + right >> 1; if(nums[mid] >= target) right = mid; else left = mid + 1; } return nums[left]==target?left:-1; } public int upBinarySearch(int[] nums,int target){ int left = 0; int right = nums.length-1; while(left < right){ int mid = left + right +1>> 1; if(nums[mid] <= target) left = mid; else right = mid-1; } return nums[left]==target?left:-1; } }
