核心观点：
1. 只要mid满足某一个条件缩小区间到[l, mid]，最终结果l/r(包括本身) 后面的都接近于满足，mid前面的数都接近于不满足这个条件。
1. 二分不一定要有序，只要目标值前面满足一个性质，后面不满足一个性质，我们就能找到这个值。
理解这个就懂了二分的应用。
接近于的意思：
如果ans > x，而x恰好在左端点，找出来的就是x，此时l/r 并不满足 ans > x 的条件，但它是最接近的。
LeetCode33 旋转数组排序
方法1：使用map来记录它原始索引和值。直接用hashMap就可以了 不需要二分
class Solution {
public int search(int[] nums, int target) {
HashMap<Integer, Integer> hashmap = new HashMap<>();
for (int i = 0; i < nums.length; i ++)
hashmap.put(nums[i], i);
// //二分
// int l = nums[0], r = nums.length - 1;
// while(l < r){
// int mid = (l + r) / 2;
// if (check(mid, target)) l = mid + 1;
// else r = mid;
// }
//装箱
Integer R = new Integer(target);
if (hashmap.containsKey(target)) return hashmap.get(target);
return -1;
}
}
方法二：二分
这个数据段是非常有特点的。
怎么使用二分呢？
二分一般对应最值问题，就是求某个值的最大或者最小，然后按照这个值慢慢逼近。
前一段满足一个性质 x >= nums[0], 后一段满足x < nums[0],那么我们通过二分就能找到前一段和后一段的分界点。
分成两端来讨论。这两端都是满足一个性质的： target前面的满足nums[x] >= target。
再进行二分就可以求解了。
class Solution {
public int search(int[] nums, int target) {
//找到分界点,要注意如果只有一个值，不会执行第一个while，返回的和实际意义不一样，所以要特别说明
if (nums.length == 1) return (nums[0] == target) ? 0 : -1;
int l = 0, r = nums.length - 1;
//这里不能使用 l = mid + 1的模板
while(l < r){
int mid = (l + r + 1) / 2;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
if (target >= nums[0]) {
l = 0;
}else
{l = l + 1; r = nums.length - 1;}
//再次二分
while (l < r){
int mid = (l + r) / 2;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[r] == target) return r;
return -1;
}
}
搜索旋转排序数组 II
题目和数据都出的不行，导致有很多地方要处理细节，这里不放上来了
寻找旋转排序数组中的最小值类似，特别处理一下升序数组
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
if (nums.length == 1 || nums[r] > nums[l]) return nums[0];
//这里不能使用 l = mid + 1的模板
while(l < r){
int mid = (l + r + 1) / 2;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
return nums[r + 1];
}
}
class Solution {
public int findMin(int[] nums) {
//找到分界点,要注意如果只有一个值，不会执行第一个while，返回的和实际意义不一样，所以要特别说明
int l = 0, r = nums.length - 1;
if (nums.length == 1 || nums[r] > nums[l]) return nums[0];
while(r >= 0 && nums[r] == nums[0]) r--;
if (r < 0) return nums[0];
//这里不能使用 l = mid + 1的模板
while(l < r){
int mid = (l + r + 1) / 2;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
return nums[r + 1];
}
}
二分
如果mid < nums[mid + 1] 右边一定有峰值， 如果mid > nums[mid + 1] 包括mid左边一定有峰值。
这样就划分了mid前后两个区间。
代码
class Solution {
public int findPeakElement(int[] nums) {
//如果mid < nums[mid + 1] 右边一定有峰值， 如果mid > nums[mid + 1] 包括mid左边一定有峰值
//这就满足了二分的基本思想
int l = 0, r = nums.length - 1;
if (l == r) return 0;
while (l < r){
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return r;
}
}
解题思路
这道题的难点在于找到一个点，这个点前后的性质不同。
我们来看，假设二分区间为[0, len - 1]假设一个index为下标，index之后都满足citations[index] >= len - index 这个特点。index之前都满足len - index >= citations[index]的性质。
因此使用二分。
代码
class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
if (len == 1 && citations[0] == 0)return 0;
int l = 0, r = len - 1;
while (l < r)
{
int mid = (l + r) / 2;
if (citations[mid] >= len - mid) r = mid;
else l = mid + 1;
}
if (len - r <= citations[r]) return len - r;
else return 0;
}
}
解题思路
二分: [amin, mid] <= mid 的个数 <= k , [mid + 1, amax]中，<= mid的个数>=k
根据数组的性质，使用双指针算法
从0行末端开始，遇到<= mid 就加上当前行的元素个数。又因为列递增，只需要考虑下行同列的元素<=mid.这样列指针就是一直向左的。相当于遍历一遍。O(N+M)= o(n)
总复杂度O(n * LOGN)
代码
class Solution {
public int kthSmallest(int[][] matrix, int k) {
//二分: [amin, ans] <= ans 的个数 <= k , [ans + 1, amax]中，<= ans个数>=k
//双指针求是否<=ans的个数
int m = matrix.length, n = matrix[0].length;
int l = matrix[0][0], r = matrix[m - 1][n - 1];
while (l < r)
{
//要去k的左端点不能是右端点，因为<= x的个数，x的取值[matrix[index], matrix[index + 1])
//index为答案的下标
int mid = (l + r) / 2;
if(get(mid, matrix) >= k)r = mid;
else l = mid + 1;
}
return r;
}
public int get(int mid, int[][] matrix){
int res = 0;
for (int i = 0, j = matrix[0].length - 1; i < matrix.length; i ++)
{
while(j >= 0 && matrix[i][j] > mid)j--;
res += j + 1;
}
return res;
}
}
解题思路
经典的二分+双指针
根据乘法表的规律可以使用双指针求<= x 的个数
同时<=x 的个数 >= k的时候，进入到左区间。反之进入右区间
最后就是找出了一个最小的x，使得<=x的个数 <= k,x就是第k个最小的数。
注意一点：一定是<k进入右区间， <=k 进入右区间找出来的是 最大的x（<=x的个数 <= k），乘法表中不一定存在。
代码
class Solution {
public int findKthNumber(int m, int n, int k) {
//<=mid的个数>=k r = mid ，找最小的mid
//打表会爆内存
int l = 1, r = 1;
r = m * n;
//System.out.println(r);
while (l < r){
int mid = (l + r) / 2;
int res = 0;
for (int i = 0, j = n - 1; i < m; i ++){
while (j >= 0 && (i + 1) * (j + 1) > mid)j --;
res += j + 1;
}
if (res >= k) r = mid;
else l = mid + 1;
}
return l;
}
}
解题思路
定义最小距离是mid，那么当第k个最小数对的距离为mid时，满足<=mid的数对个数<=k符合二分的思想
同时使用双指针求出<=某一距离的数对的个数,前提是nums数组有序。
for(int i = 0, j = 0; i < nums.length; i ++)
{
while(nums[i] - nums[j] > mid) j++;
res += i - j;
}
注意我们要求第k个最小数对，也就是找到k的左边界点。
if(res >= k)r = mid 找的才是左边界点。
代码
class Solution {
public int smallestDistancePair(int[] nums, int k) {
//定义第k个最小距离是mid，那么<=mid的数对个数<=k, >mid的数对个数>k
//通过二分就能找到最小数对了
//如何求<= mid 的距离对数有多少个? 使用双指针
//直接构造最小距离数组会超时
int m = nums.length;
Arrays.sort(nums);
int l = 0, r = 0;
for (int i = 0; i < m; i ++)
{
r = Math.max(r, nums[i]);
}
while (l < r){
int mid = (l + r) / 2;
if (check(mid,nums ,k)) r = mid;
else l = mid + 1;
}
return r;
}
public boolean check(int mid,int[] nums ,int k){
//如何求<= mid 的距离对数有多少个? 使用双指针
int res = 0;
for(int i = 0, j = 0; i < nums.length; i ++)
{
while(nums[i] - nums[j] > mid) j++;
res += i - j;
}
if (res >= k) return true;
else return false;
}
}
后续更新…
