目录
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++;
else
return 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;
//右边是往上，一定能找到波峰
else
left = 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位置的数加1
public 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++){
//较短的版本号后续都取0
String 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;
}
}