本系列為筆者的 Leetcode 刷題記錄，順序為 Hot 100 題官方順序，根據(jù)標簽命名，記錄筆者總結的做題思路，附部分代碼解釋和疑問解答，01~07為C++語言，08及以后為Java語言。

01 搜索插入位置

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while(left <= right){int mid = (left + right) / 2;if(nums[mid] == target){return mid;}else if(nums[mid] < target){left = mid + 1;}else{right = mid - 1;}}return left;}
}

02 搜索二維矩陣

class Solution {public boolean searchMatrix(int[][] matrix, int target) {//思路：將二維數(shù)組展開為一維數(shù)組int row = matrix.length;int column = matrix[0].length;int left = 0;int right = row * column - 1;while(left <= right){int mid = (left + right) / 2;int x = matrix[mid / column][mid % column];if(x == target){return true;}else if(x < target){left = mid + 1;}else{right = mid - 1;}}return false;}
}

03 在排序數(shù)組中查找元素的第一個和最后一個位置

class Solution {public int[] searchRange(int[] nums, int target) {int[] positions = new int[]{-1, -1};int left1 = 0, left2 = 0;int right1 = nums.length-1, right2 = nums.length-1;//尋找第一個等于target的位置while(left1 <= right1){int mid1 = (left1 + right1) / 2;if(nums[mid1] == target){positions[0] = mid1;right1 = mid1 - 1; //重點}else if(nums[mid1] < target){left1 = mid1 + 1;}else{right1 = mid1 - 1;}}//尋找最后一個等于target的位置while(left2 <= right2){int mid2 = (left2 + right2) / 2;if(nums[mid2] == target){positions[1] = mid2;left2 = mid2 + 1; //重點}else if(nums[mid2] < target){left2 = mid2 + 1;}else{right2 = mid2 - 1;}}return positions;}
}

第一個重點確保了即使找到目標值，也會繼續(xù)向左搜索，以確保找到第一個出現(xiàn)的索引。

第二個重點確保了即使找到目標值，也會繼續(xù)向右搜索，以確保找到最后一個出現(xiàn)的索引。

04 搜索旋轉排序數(shù)組 ?

class Solution {public int search(int[] nums, int target) {int n = nums.length;//特殊情況判斷if(n == 0){return -1;}if(n == 1){return nums[0] == target ? 0 : -1;}int left = 0;int right = n - 1;while(left <= right){int mid = (left + right) / 2;if(nums[mid] == target){return mid;}else if(nums[0] <= nums[mid]){ //大山峰、小山峰if(nums[0] <= target && target < nums[mid]){right = mid - 1;}else{left = mid + 1;}}else{ //小山峰、大山峰if(nums[mid] < target && target <= nums[n - 1]){left = mid + 1;}else{right = mid - 1;}}}return -1;}
}

05 尋找旋轉排序數(shù)組中的最小值

class Solution {public int findMin(int[] nums) {int n = nums.length;//特殊情況判斷if(n == 1){return nums[0];}int left = 0;int right = n - 1;int flag = nums[0];while(left <= right){int mid = (left + right) / 2;flag = nums[mid] < flag ? nums[mid] : flag;if(nums[0] <= nums[mid]){ //大山峰、小山峰left = mid + 1;}else{ //小山峰、大山峰right = mid - 1;}}return flag;}
}

06 尋找兩個正序數(shù)組的中位數(shù)

如果對時間復雜度的要求有log，通常都需要用到二分查找。

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int numsLength = m + n;if(numsLength % 2 == 1){int mid = numsLength / 2 + 1;double ans = myFunction(nums1, nums2, mid); //尋找第k小的數(shù)return ans;}else{int mid1 = numsLength / 2;int mid2 = numsLength / 2 + 1;double ans = (myFunction(nums1, nums2, mid1) + myFunction(nums1, nums2, mid2)) / 2.0;return ans;}}public int myFunction(int[] nums1, int[] nums2, int k){int m = nums1.length, n = nums2.length;int index1 = 0, index2 = 0;while(true){//特殊情況判斷if(index1 == m){return nums2[index2 + k - 1];}if(index2 == n){return nums1[index1 + k - 1];}if(k == 1){return Math.min(nums1[index1], nums2[index2]);}int half = k / 2;int newIndex1 = Math.min(index1 + half, m) - 1;int newIndex2 = Math.min(index2 + half, n) - 1;int pivot1 = nums1[newIndex1];int pivot2 = nums2[newIndex2];//重點if(pivot1 <= pivot2){k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;}else{k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}
}