06排序 + 查找（D2_查找（D2_刷题练习））

目录

1. 二分查找-I

1.1 题目描述

1.2 解题思路

方法：二分法（推荐使用）

2. 二维数组中的查找

2.1 题目描述

2.2 解题思路

方法一：二分查找（推荐使用）

3. 寻找峰值

3.1 题目描述

3.2 解题思路

方法一：二分查找（推荐使用）

4. 数组中的逆序对

4.1 题目描述

4.2 解题思路

方法一：归并排序(推荐使用)

方法二：树状数组（扩展思路）

5. 旋转数组的最小数字

5.1 题目描述

5.2 解题思路

方法一：二分法（推荐使用）

方法二：遍历查找（扩展思路）

6. 比较版本号

6.1 题目描述

6.2 解题思路

方法一：双指针遍历截取（推荐使用）

方法二：分割截取（思路扩展）

7. 寻找文件副本

7.1 题目描述

7.2 解题思路

方法一：哈希表

方法二：原地交换

8. 统计目标成绩的出现次数

8.1 题目描述

8.2 解题思路

方法一：二分查找

9. 点名

9.1 题目描述

9.2 解题思路

方法一：二分查找

10. 招式拆解 II

10.1 题目描述

10.2 解题思路

方法一：哈希表

方法二：有序哈希表

11. 搜索插入位置

11.1 题目描述

11.2 解题思路

方法一：二分查找

12. 搜索二维矩阵

12.1 题目描述

12.2 解题思路

方法一：两次二分查找

方法二：一次二分查找

13. 在排序数组中查找元素的第一个和最后一个位置

13.1 题目描述

13.2 解题思路

方法一：二分查找

14. 搜索旋转排序数组

14.1 题目描述

14.2 解题思路

方法一：二分查找

15. 寻找旋转排序数组中的最小值

15.1 题目描述

15.2 解题思路

方法一：二分查找

16. 寻找两个正序数组的中位数

16.1 题目描述

16.2 解题思路

方法一：二分查找

方法二：划分数组

17. 猜数字大小

17.1 题目描述

17.2 解题思路

方法一：二分查找

18. 咒语和药水的成功对数

18.1 题目描述

18.2 解题思路

方法一：二分查找

方法二：双指针

19. 爱吃香蕉的珂珂

19.1 题目描述

19.2 解题思路

方法一：二分查找

---

1. 二分查找-I

1.1 题目描述

1.2 解题思路

方法：二分法（推荐使用）

Java实现代码：

import java.util.*;
public class Solution {public int search (int[] nums, int target) {int l = 0;int r = nums.length - 1;//从数组首尾开始，直到二者相遇while(l <= r){ //每次检查中点的值int m = (l + r) / 2; if(nums[m] == target)return m;//进入左的区间if(nums[m] > target) r = m - 1;//进入右区间else l = m + 1;}//未找到return -1; }
}

2. 二维数组中的查找

2.1 题目描述

2.2 解题思路

方法一：二分查找（推荐使用）

Java实现代码：

public class Solution {public boolean Find(int target, int [][] array) {//优先判断特殊if(array.length == 0)  return false;int n = array.length;if(array[0].length == 0)  return false;int m = array[0].length;//从最左下角的元素开始往左或往上for(int i = n - 1, j = 0; i >= 0 && j < m; ){ //元素较大，往上走if(array[i][j] > target)   i--;//元素较小，往右走else if(array[i][j] < target) j++;elsereturn true;}return false;}
}

3. 寻找峰值

3.1 题目描述

3.2 解题思路

方法一：二分查找（推荐使用）

Java实现代码：

import java.util.*;
public class Solution {public int findPeakElement (int[] nums) {int left = 0;int right = nums.length - 1;//二分法while(left < right){ int mid = (left + right) / 2;//右边是往下，不一定有坡峰if(nums[mid] > nums[mid + 1])right = mid;//右边是往上，一定能找到波峰elseleft = mid + 1;}//其中一个波峰return right; }
}

4. 数组中的逆序对

4.1 题目描述

4.2 解题思路

方法一：归并排序(推荐使用)

Java实现代码：

public class Solution {public int mod = 1000000007;public int mergeSort(int left, int right, int [] data, int [] temp){//停止划分if(left >= right)    return 0;//取中间int mid = (left + right) / 2; //左右划分合并int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); //防止溢出res %= mod;  int i = left, j = mid + 1;for(int k = left; k <= right; k++)temp[k] = data[k];for(int k = left; k <= right; k++){if(i == mid + 1)data[k] = temp[j++];else if(j == right + 1 || temp[i] <= temp[j])data[k] = temp[i++];//左边比右边大，答案增加else{ data[k] = temp[j++];// 统计逆序对res += mid - i + 1; }}return res % mod;}public int InversePairs(int [] array) {int n = array.length;int[] res = new int[n];return mergeSort(0, n - 1, array, res);}
}

方法二：树状数组（扩展思路）

import java.util.*;
class BIT {private int[] tree;private int n;//初始化树状数组的大小public BIT(int m) { this.n = m;this.tree = new int[m + 1];}//使数组呈现2、4、8、16这种树状public int lowbit(int x) { return x & (-x);}//查询序列1到x的前缀和public int query(int x) { int res = 0;while(x != 0){res += tree[x];x -= lowbit(x);}return res;}//序列x位置的数加1public void update(int x) { while(x <= n){tree[x]++;x += lowbit(x);}}
}public class Solution {public int mod = 1000000007;public int InversePairs(int [] array) {int n = array.length;int[] temp = new int[n];System.arraycopy(array, 0, temp, 0, n);//排序得到一份有序的数组Arrays.sort(temp); //二分法重新映射，将数字变成其在有序数组中的位置for (int i = 0; i < n; ++i) //二分法查找在其在有序数组中的位置array[i] = Arrays.binarySearch(temp, array[i]) + 1;//建立大小为n的树状数组BIT bit = new BIT(n); int res = 0;//统计逆序对for(int i = 0; i < n; i++){ //前缀和做差res = (res + bit.query(n) - bit.query(array[i])) % mod;bit.update(array[i]);}return res;}
}

5. 旋转数组的最小数字

5.1 题目描述

5.2 解题思路

方法一：二分法（推荐使用）

Java实现代码：

import java.util.ArrayList;
public class Solution {public int minNumberInRotateArray(int [] array) {int left = 0;int right = array.length - 1;while(left < right){int mid = (left + right) / 2;//最小的数字在mid右边if(array[mid] > array[right]) left = mid + 1;//无法判断，一个一个试else if(array[mid] == array[right]) right--;//最小数字要么是mid要么在mid左边else right = mid;}return array[left];}
}

方法二：遍历查找（扩展思路）

import java.util.*;
public class Solution {public int minNumberInRotateArray(int [] array) {//数组一定有元素int res = array[0]; //遍历数组for(int i = 1; i < array.length; i++) //每次维护最小值res = Math.min(res, array[i]); return res;}
}

6. 比较版本号

6.1 题目描述

6.2 解题思路

方法一：双指针遍历截取（推荐使用）

Java实现代码：

import java.util.*;
public class Solution {public int compare (String version1, String version2) {int n1 = version1.length();int n2 = version2.length();int i = 0, j = 0;//直到某个字符串结束while(i < n1 || j < n2){long num1 = 0;//从下一个点前截取数字while(i < n1 && version1.charAt(i) != '.'){ num1 = num1 * 10 + (version1.charAt(i) - '0');i++;}//跳过点i++; long num2 = 0;//从下一个点前截取数字while(j < n2 && version2.charAt(j) != '.'){ num2 = num2 * 10 + (version2.charAt(j) - '0');j++;}//跳过点j++; //比较数字大小if(num1 > num2) return 1;if(num1 < num2)return -1;}//版本号相同return 0; }
}

方法二：分割截取（思路扩展）

import java.util.*;
public class Solution {public int compare (String version1, String version2) {//按照.划分String[] nums1 = version1.split("\\."); String[] nums2 = version2.split("\\.");for(int i = 0; i < nums1.length || i < nums2.length; i++){//较短的版本号后续都取0String str1 = i < nums1.length ? nums1[i] : "0"; String str2 = i < nums2.length ? nums2[i] : "0";long num1 = 0;//字符串转数字for(int j = 0; j < str1.length(); j++) num1 = num1 * 10 + (str1.charAt(j) - '0');long num2 = 0;for(int j = 0; j < str2.length(); j++)num2 = num2 * 10 + (str2.charAt(j) - '0');//比较数字大小if(num1 > num2) return 1;if(num1 < num2)return -1;}//版本相同return 0;}
}

7. 寻找文件副本

7.1 题目描述

7.2 解题思路

方法一：哈希表

class Solution {public int findRepeatDocument(int[] documents) {Set<Integer> hmap = new HashSet<>();for(int doc : documents) {if(hmap.contains(doc)) return doc;hmap.add(doc);}return -1;}}

方法二：原地交换

class Solution {public int findRepeatDocument(int[] documents) {int i = 0;while(i < documents.length) {if(documents[i] == i) {i++;continue;}if(documents[documents[i]] == documents[i]) return documents[i];int tmp = documents[i];documents[i] = documents[tmp];documents[tmp] = tmp;}return -1;}}

8. 统计目标成绩的出现次数

8.1 题目描述

8.2 解题思路

方法一：二分查找

class Solution {public int countTarget(int[] scores, int target) {int leftIdx = binarySearch(scores, target, true);int rightIdx = binarySearch(scores, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < scores.length && scores[leftIdx] == target && scores[rightIdx] == target) {return rightIdx - leftIdx + 1;} return 0;}public int binarySearch(int[] nums, int target, boolean lower) {int left = 0, right = nums.length - 1, ans = nums.length;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}

9. 点名

9.1 题目描述

9.2 解题思路

方法一：二分查找

class Solution {public int takeAttendance(int[] records) {int i = 0, j = records.length - 1;while(i <= j) {int m = (i + j) / 2;if(records[m] == m) i = m + 1;else j = m - 1;}return i;}}

10. 招式拆解 II

10.1 题目描述

10.2 解题思路

方法一：哈希表

class Solution {public char dismantlingAction(String arr) {HashMap<Character, Boolean> hmap = new HashMap<>();char[] sc = arr.toCharArray();for(char c : sc)hmap.put(c, !hmap.containsKey(c));for(char c : sc)if(hmap.get(c)) return c;return ' ';}}

方法二：有序哈希表

class Solution {public char dismantlingAction(String arr) {Map<Character, Boolean> hmap = new LinkedHashMap<>();char[] sc = arr.toCharArray();for(char c : sc)hmap.put(c, !hmap.containsKey(c));for(Map.Entry<Character, Boolean> d : hmap.entrySet()){if(d.getValue()) return d.getKey();}return ' ';}}

11. 搜索插入位置

11.1 题目描述

11.2 解题思路

方法一：二分查找

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

12. 搜索二维矩阵

12.1 题目描述

12.2 解题思路

方法一：两次二分查找

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int rowIndex = binarySearchFirstColumn(matrix, target);if (rowIndex < 0) {return false;}return binarySearchRow(matrix[rowIndex], target);}public int binarySearchFirstColumn(int[][] matrix, int target) {int low = -1, high = matrix.length - 1;while (low < high) {int mid = (high - low + 1) / 2 + low;if (matrix[mid][0] <= target) {low = mid;} else {high = mid - 1;}}return low;}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}

方法二：一次二分查找

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

13. 在排序数组中查找元素的第一个和最后一个位置

13.1 题目描述

13.2 解题思路

方法一：二分查找

class Solution {public int[] searchRange(int[] nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {return new int[]{leftIdx, rightIdx};} return new int[]{-1, -1};}public int binarySearch(int[] nums, int target, boolean lower) {int left = 0, right = nums.length - 1, ans = nums.length;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}

14. 搜索旋转排序数组

14.1 题目描述

14.2 解题思路

方法一：二分查找

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 l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) {return mid;}if (nums[0] <= nums[mid]) {if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return -1;}
}

15. 寻找旋转排序数组中的最小值

15.1 题目描述

15.2 解题思路

方法一：二分查找

class Solution {public int findMin(int[] nums) {int low = 0;int high = nums.length - 1;while (low < high) {int pivot = low + (high - low) / 2;if (nums[pivot] < nums[high]) {high = pivot;} else {low = pivot + 1;}}return nums[low];}
}

16. 寻找两个正序数组的中位数

16.1 题目描述

16.2 解题思路

方法一：二分查找

 

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 = nums1.length, length2 = nums2.length;int totalLength = length1 + length2;if (totalLength % 2 == 1) {int midIndex = totalLength / 2;double median = getKthElement(nums1, nums2, midIndex + 1);return median;} else {int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;return median;}}public int getKthElement(int[] nums1, int[] nums2, int k) {/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较* 这里的 "/" 表示整除* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个* 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个* 这样 pivot 本身最大也只能是第 k-1 小的元素* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组* 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数*/int length1 = nums1.length, length2 = nums2.length;int index1 = 0, index2 = 0;int kthElement = 0;while (true) {// 边界情况if (index1 == length1) {return nums2[index2 + k - 1];}if (index2 == length2) {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, length1) - 1;int newIndex2 = Math.min(index2 + half, length2) - 1;int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];if (pivot1 <= pivot2) {k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;} else {k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}
}

方法二：划分数组

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.length;int n = nums2.length;int left = 0, right = m;// median1：前一部分的最大值// median2：后一部分的最小值int median1 = 0, median2 = 0;while (left <= right) {// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]int i = (left + right) / 2;int j = (m + n + 1) / 2 - i;// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);if (nums_im1 <= nums_j) {median1 = Math.max(nums_im1, nums_jm1);median2 = Math.min(nums_i, nums_j);left = i + 1;} else {right = i - 1;}}return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;}
}

17. 猜数字大小

17.1 题目描述

17.2 解题思路

方法一：二分查找

public class Solution extends GuessGame {public int guessNumber(int n) {int left = 1, right = n;while (left < right) { // 循环直至区间左右端点相同int mid = left + (right - left) / 2; // 防止计算时溢出if (guess(mid) <= 0) {right = mid; // 答案在区间 [left, mid] 中} else {left = mid + 1; // 答案在区间 [mid+1, right] 中}}// 此时有 left == right，区间缩为一个点，即为答案return left;}
}

18. 咒语和药水的成功对数

18.1 题目描述

18.2 解题思路

方法一：二分查找

class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {Arrays.sort(potions);int n = spells.length, m = potions.length;int[] res = new int[n];for (int i = 0; i < n; i++) {long t = (success + spells[i] - 1) / spells[i] - 1;res[i] = m - binarySearch(potions, 0, m - 1, t);}return res;}public int binarySearch(int[] arr, int lo, int hi, long target) {int res = hi + 1;while (lo <= hi) {int mid = lo + (hi - lo) / 2;if (arr[mid] > target) {res = mid;hi = mid - 1;} else {lo = mid + 1;}}return res;}
}

方法二：双指针

class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {int n = spells.length, m = potions.length;int[] res = new int[n];int[][] idx = new int[n][2];for (int i = 0; i < n; ++i) {idx[i][0] = spells[i];idx[i][1] = i;}Arrays.sort(potions);for (int i = 0, j = m - 1; i < j; ++i, --j) {int temp = potions[i];potions[i] = potions[j];potions[j] = temp;}Arrays.sort(idx, (a, b) -> a[0] - b[0]);for (int i = 0, j = 0; i < n; ++i) {int p = idx[i][1];int v = idx[i][0];while (j < m && (long) potions[j] * v >= success) {++j;}res[p] = j;}return res;}
}

19. 爱吃香蕉的珂珂

19.1 题目描述

19.2 解题思路

方法一：二分查找

class Solution {public int minEatingSpeed(int[] piles, int h) {int low = 1;int high = 0;for (int pile : piles) {high = Math.max(high, pile);}int k = high;while (low < high) {int speed = (high - low) / 2 + low;long time = getTime(piles, speed);if (time <= h) {k = speed;high = speed;} else {low = speed + 1;}}return k;}public long getTime(int[] piles, int speed) {long time = 0;for (int pile : piles) {int curTime = (pile + speed - 1) / speed;time += curTime;}return time;}
}