1 二分查找
public int binarySearch(int[] nums, int target) { //write your code here if (nums.length == 0) return -1; int start = 0; int end = nums.length - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (nums[mid] >= target) { end = mid; } else { start = mid + 1; } } return nums[start] == target ? start : -1; }
2 搜索区间
public int[] searchRange(int[] a, int target) { int[] res = {-1, -1}; if (a.length == 0) return res; int start = 0; int end = a.length - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (a[mid] >= target) { end = mid; } else { start = mid + 1; } } if (a[start] != target) { return res; } res[0] = start; end = a.length - 1; while (start < end) { mid = start + (end - start) / 2 + 1; if (a[mid] <= target) { start = mid; } else { end = mid - 1; } } res[1] = end; return res; }
3 搜索插入位置
public int searchInsert(int[] a, int target) { // write your code here if (a.length == 0) { return 0; } if (a[a.length - 1] < target) { return a.length; } int start = 0; int end = a.length - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (a[mid] == target) { return mid; } else if (a[mid] < target) { start = mid + 1; } else { end = mid; } } return start;
4 搜索旋转排序数组
public int search(int[] a, int target) { if (a == null || a.length == 0) { return -1; } int start = 0; int end = a.length - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (a[mid] == target) { return mid; } if (a[start] <= a[mid]) { if (a[start] <= target && target < a[mid]){ end = mid; } else { start = mid + 1; } } else { if (a[mid] < target && target <= a[end]) { start = mid + 1; } else { end = mid; } } } return a[start] == target ? start : -1; }
5 搜索旋转排序数组 II
public boolean search(int[] a, int target) { // write your code here if (a == null || a.length == 0) { return false; } int l = 0; int r = a.length - 1; while (l < r) { int m = (l + r)/2; if (a[m] == target) { return true; } if (a[m] > a[l]) { if (a[m] > target && a[l] <= target) { r = m; } else { l = m + 1; } } else if (a[m] < a[l]) { if (a[m] < target && a[r] >= target) { l = m + 1; } else { r = m; } } else { l++; } } return a[l] == target; }
6 搜索二维矩阵
public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int m = matrix.length; int n = matrix[0].length; int start = 0; int end = m * n - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (matrix[mid / n][mid % n] == target) { return true; } else if (matrix[mid / n][mid % n] < target) { start = mid + 1; } else { end = mid; } } return matrix[start / n][start % n] == target; }
7 第一个错误的代码版本
public int findFirstBadVersion(int n) { // write your code here int start = 1; int end = n; int mid; if (n == 1 && SVNRepo.isBadVersion(1)) return 1; while (start < end) { mid = start + (end - start) / 2; if (!SVNRepo.isBadVersion(mid)) { start = mid + 1; } else { end = mid; } } return start; }
8 寻找峰值
-
View Cod
public int findPeak(int[] a) { // write your code here if (a == null || a.length <= 2) return -1; int start = 0; int end = a.length - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (a[mid] < a[mid + 1]){ start = mid + 1; } else { end = mid; } } return start; }
9 寻找旋转排序数组中的最小值
public int findMin(int[] nums) { // write your code here if (nums.length == 1) { return nums[0]; } int start = 0; int end = nums.length - 1; int mid; while (start < end) { if (nums[start] < nums[end]) { return nums[start]; } mid = start + (end - start) / 2; if (nums[mid] >= nums[start]) { start = mid + 1; } else { end = mid; } } return nums[start]; }
不熟悉
10 寻找旋转排序数组中的最小值 II
public int findMin(int[] num) { // write your code herem int start = 0; int end = num.length - 1; int mid; while (start < end) { if (num[start] < num[end]) { return num[start]; } mid = start + (end - start) / 2; if (num[start] < num[mid]) { start = mid + 1; } else if (num[start] > num[mid]){ end = mid; } else { start++; } } return num[start]; }
11 x的平方根
public int sqrt(int x) { if (x < 0) return -1; if (x == 0) return 0; int start = 1; int end = x / 2 + 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (mid <= x / mid && mid + 1 > x / (mid + 1)) { return mid; } else if (mid > x / mid) { end = mid; } else { start = mid + 1; } } if (start <= x / start && start + 1 > x / (start + 1)) { return start; } return -1; }
12 Remove Duplicates from Sorted Array
public int removeDuplicates(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int index = 0; for (int i = 1; i < nums.length; i++) { if (nums[index] != nums[i]) { nums[++index] = nums[i]; } } return index + 1; }
13 Remove Duplicates from Sorted Array II
public int removeDuplicates(int[] nums) { // write your code here if (nums.length < 2) { return nums.length; } int index = 2; for (int i = 2; i < nums.length; i++) { if (nums[i] != nums[index - 2]) { nums[index++] = nums[i]; } } return index; }
不熟练
14 Merge Sorted Array
public void mergeSortedArray(int[] a, int m, int[] b, int n) { if (a == null || b == null) { return; } int idx1 = m - 1; int idx2 = n - 1; int len = m + n - 1; while (idx1 >= 0 && idx2 >= 0) { if (a[idx1] > b[idx2]) { a[len--] = a[idx1--]; } else { a[len--] = b[idx2--]; } } while (idx2 >= 0) { a[len--] = b[idx2--]; } }
15 Median of two Sorted Arrays
public double findMedianSortedArrays(int[] a, int[] b) { int m = a.length; int n = b.length; int l = (m + n + 1) / 2; int r = (m + n + 2) / 2; return (find(a, 0, m - 1, b, 0, n - 1, l) + find(a, 0, m - 1, b, 0, n - 1, r)) / 2.0; } public int find(int[] a, int as, int ae, int[] b, int bs, int be, int k) { if (as >= a.length) return b[bs + k - 1]; if (bs >= b.length) return a[as + k - 1]; if (k == 1) { return Math.min(a[as], b[bs]); } int am = (as + k / 2 - 1 >= a.length) ? Integer.MAX_VALUE : a[as + k / 2 - 1]; int bm = (bs + k / 2 - 1 >= b.length) ? Integer.MAX_VALUE : b[bs + k / 2 - 1]; if (am < bm) { return find(a, as + k / 2, ae, b, bs, be, k - k / 2); } else { return find(a, as, ae, b, bs + k / 2, be, k - k / 2); } }