二分查找总结
2019-11-11 本文已影响0人
Tim在路上
二分查找是在每次匹配后,将查找的空间一分为二的算法,二分查找应该是有序的数组进行查找.
二分查找模板
1. 模板一
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}
模板一,
初始条件 , left = 0, right = nums.length - 1
终止 left > right
向左查找：right = mid-1
向右查找：left = mid+1
不需要后序的处理,因为每一步都在, 进行遍历会遍历所有的可能,当条件结束一定是不满足条件
2. 模板二
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.length && nums[left] == target) return left;
return -1;
}
它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
模板二,
初始条件: left = 0, right = nums.length;
终止条件 left == right
向左查找：right = mid
向右查找：left = mid+1
需要最终判断 ,left 没有出界的情况下, left 是否是最终的答案
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
3.模板三
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
初始条件: left = 0, right = nums.length - 1;
终止条件: left + 1 == right
向左查找：right = mid
向右查找：left = mid
它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。
最后需要判断最后的两个元素,left 和 right 是否是最后的结果
模板四
不进行判断,直接进行返回最终的迭代值
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
这种模板主要用于,首先边界值不能超出,同时条件判断需要两个值同时判断的问题
我们让right 的更新包括mid,让left 的更新 +1
最后留下的一个元素就是最终要的元素, right 的判断就必须包括答案的最终条件
二分法左右边界定位
// 重复或不存在时，返回左边界
public int binarySearch(int[] nums,int target){
int left = 0,right = nums.length-1;
while(left<right){
int mid = left + (right - left)/2;
if (nums[mid] >= target){
high = mid;
}else{
low = mid + 1;
}
}
if(nums[low] == target){
return low;
}
return -1;
}
// 最后的一次出现右边界的位置
public int binarySearch(int[] nums,int target){
int left = 0,right = nums.length-1;
while(left < right){
// 注意这里一定要加1 否则会出现死循环
int mid = left + (right - left + 1)/2;
if（nums[mid] <= target）{
low = mid;
}else{
high = mid -1;
}
}
if(nums[low] == target){
return low;
}
return -1;
}
upper 和 lower
// lower_bound 是找到第一个大于等于目标值的数
private static int lower_bound(int[] nums, int key) {
int low = 1,hig = nums.length;
while (low < hig) {
int mid = low + ((hig - low) >> 1);
if (nums[mid] >= key) hig = mid;
else low = mid + 1;
}
return low;
}
// upper bound 是找到第一个 大于目标值的数
private static int upper_bound(int[] nums,int key){
int low = 1,hig = nums.length-1;
while (low < hig) {
int mid = low + ((hig - low) >> 1);
if (nums[mid] <= key) low = mid + 1;
else hig = mid;
}
return low;
}
模板一
// 求 x 的开方值
public int mySqrt(int x) {
if (x < 2){
return x;
}
int left = 1, right = x/2 + 1;
while (left <= right){
int mid = left + (right - left)/2;
if (mid == x/mid){
return mid;
}else if (mid > x/mid){
right = mid - 1;
}else {
left = mid + 1;
}
}
// 模板一,退出循环一定是没有查询到等号要求的值
// 没有查找到具体的相等的, 返回刚好小于的
return right;
}
// 在旋转数组中进行查找
思路:
如果 中间值等于 目标值直接返回
如果目标值大于nums[0] (他会包括 正常没旋转的情况)
- 只有中间值大于等于nums[0], 中间值小于目标值 left = mid + 1,其他情况都是减
如果目标值小于nums[0], 说明数组一定旋转了 - 只有中间值也小于nums[0], 中间值大于 目标值 right = mid -1 ,其他都是加
在讨论情况是要确定一个简单的同时是一定的,那么剩下的就是相反的,只用确定一个条件即可
public int search(int[] nums, int target) {
int left = 0,right = nums.length -1;
while (left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
return mid;
}
if (target >= nums[0]){
if (nums[mid] >= nums[0] && nums[mid] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}else {
if (nums[mid] < nums[0] && nums[mid] > target){
right = mid - 1;
}else {
left = mid + 1;
}
}
}
return -1;
}
模板二
我们不判断是否等于,这里需要判断连续的两个值,可以转换为两个方向的夹逼
public int findPeakElement(int[] nums) {
int left = 0,right = nums.length;
while (left < right){
int mid = left + (right - left)/2;
// 这里 mid 和 mid + 1 是我们要判断的数字,mid + 1 是不会越界的
// nums[-1] = nums[n] = -∞ 保证通过这种条件可以找到峰值
if (nums[mid] > nums[mid+1]){
right = mid;
}else {
left = mid + 1;
}
}
return left;
}
public int firstBadVersion(int n) {
int left = 1;
// right 一定不能变成 n + 1 因为可能会超出int的边界值 // 而第二种最后的 超出边界返回你
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if(isBadVersion(mid)){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
public int findMin(int[] nums) {
if (nums.length == 0){
return nums[0];
}
if (nums[0] < nums[nums.length-1]){
return nums[0];
}
int left = 0, right = nums.length-1;
while (left < right){
int mid = left + (right - left)/2;
if (nums[mid] < nums[0]){
right = mid;
}else {
left = mid + 1;
}
}
return nums[left];
}
// 查询目标值,返回数组中目标值的起始值和最终值
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0){
return new int[]{-1,-1};
}
int start = 0;
int end = nums.length -1;
int left = 0,right = nums.length-1;
while (left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
int i = mid;
while (--i >= start){
if (nums[i] != nums[mid]){
break;
}
}
start = i+1;
i = mid;
while (++i <= end){
if (nums[i] != nums[mid]){
break;
}
}
end = i-1;
return new int[]{start,end};
}else if (nums[mid] > target){
right = mid -1;
}else {
left = mid + 1;
}
}
return new int[]{-1,-1};
}
// 找寻两个排序数组中的中位数
将两个数组进行合并, 然后将数组中的一半+1 放到新数组中,然后选出最终的结果
public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if (m == 0){
if (n % 2 == 0){
return (nums2[n/2-1] + nums2[n/2])/2.0;
}else {
return nums2[n/2];
}
}
if (n == 0){
if (m % 2 == 0){
return (nums1[m/2-1] + nums1[m/2])/2.0;
}else {
return nums1[m/2];
}
}
int i =0,j=0;
int index = 0;
int max = (m+n)/2+1;
int[] num = new int[max];
while (index < max){
if (i >= m){
num[index++] = nums2[j++];
}else if (j >= n){
num[index++] = nums1[i++];
}else if (nums1[i] <= nums2[j]){
num[index++] = nums1[i++];
}else {
num[index++] = nums2[j++];
}
}
if ((m + n) %2 == 0){
return (num[(m+n)/2-1] + num[((m+n)/2)])/2.0;
}else {
return num[(m+n)/2];
}
}
// 使用两个变量保存到中间值即可
// 使用两个变量保存最后两个数,遍历到 len/2
public double findMedianSortedArrays3(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1,right = -1;
int aStart = 0,bStart = 0;
for (int i=0;i<=len/2;i++){
left = right;
if (aStart<m && (bStart>=n || A[aStart] < B[bStart])){
right = A[aStart++];
}else {
right = B[bStart++];
}
}
if ((len & 1) == 0){
return (left + right)/2.0;
}else {
return right;
}
}
// 使用递归的方式查询第k小方式
思路:
首先求出中间位的位数, 偶数有两个,奇数一个
然后迭代求第k大,
迭代:
首先每次保证 A 小于 B
如果 A的长度等于0 ,直接返回B 的第k个数字
如果 k 已经递减到1 直接返回 A 和 B的首数字最小值
思路就是每次 K 递减 1/2 ,然后再删除 k/2 个数字
如果 A[i] 大于 B[j] 说明 A[i] 可能是第k大 , 删除 B[j] 之前的数字
如果 B[j] 大于 A[i] 说明 B[j] 可能是第k大, 删除 A[i] 之前的数字
public double findMedianSortedArrays4(int[] A, int[] B) {
int n = A.length;
int m = B.length;
// 求中位数, +1, +2 求出的是初始从1 开始的中位数,如果相等就是奇数,否则偶数
int left = (n+m+1)/2;
int right = (n+m+2)/2;
// 将偶数和奇数合并
return (getKth(A,0,n-1,B,0,m-1,left)+ getKth(A,0,n-1,B,0,m-1,right))/2.0;
}
public int getKth(int[] A,int start1,int end1,int[] B,int start2,int end2,int k){
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if (len1 > len2){
return getKth(B,start2,end2,A,start1,end1,k);
}
if (len1 == 0){
return B[start2+k-1];
}
if (k == 1){
return Math.min(A[start1],B[start2]);
}
int i = start1 + Math.min(len1,k/2)-1;
int j = start2 + Math.min(len2,k/2)-1;
// 找到第Kth 还要保证 左边最大值小于右边最小值
if (A[i]>B[j]){
return getKth(A,start1,end1,B,j+1,end2,k - (j-start2 + 1));
}else {
return getKth(A,i+1,end1,B,start2,end2,k-(i-start1+1));
}
}
/// 查询两个数组的中位数
迭代计算,
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
// halfLen 保证 在奇数比中位数多1 ,偶数是最后的中位数
// 以 iMin = 0, iMax = m,
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
// B[j-1] 代表的是 左部的数, A[i] 代表右部的数
// 左大于右, iMin = i + 1
if (i < iMax && B[j-1] > A[i]){
iMin = i + 1; // i is too small
}
// 两个都是判断左大于右进行 移动
else if (i > iMin && A[i-1] > B[j]) {
iMax = i - 1; // i is too big
}
// 不存在左大于右,进行输出,
else { // i is perfect
// i 等于0 说明 左最大在i-1 和 j-1 中, B中,如果奇数返回 maxLeft
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
// minRight 在 i 和 j 中产生
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
// 返回 (left + right) / 2.0
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
// 两数相除
思路:
如果除数是0 ,直接返回-1
如果被除数是0,直接返回0
如果被除数是负数的最小值,同时除数是负数-1,那么直接返回最大值
判断是不是负数 两数进行异或 如果小于0 表明是负数
首先将数都转换为long型的正数, 用一个变量div_count保存每次加的值
被除数 减去 除数 , 结果 + div_count
然后 除数 加倍 div_count 加倍
中间需要处理的情况,如果 被除数 小于 初始除数 break
如果 被除数 减 当前除数 剩余 小于当前除数,那么就不进行加倍,除数还原,div_count 还原
public int divide(int dividend, int divisor) {
if (divisor == 0){
return -1;
}
if (dividend == 0){
return 0;
}
if (dividend == Integer.MIN_VALUE && divisor == -1){
return Integer.MAX_VALUE;
}
boolean negetive = (dividend^divisor)<0;
int res = 0, div_count = 1;
long dividend_tmp = Math.abs((long)dividend);
long divisor_tmp = Math.abs((long)divisor);
while (dividend_tmp>=divisor_tmp){
dividend_tmp -= divisor_tmp;
res += div_count;
if (dividend_tmp < Math.abs((long)divisor)){
break;
}
if (dividend_tmp-divisor_tmp < divisor_tmp){
divisor_tmp = Math.abs((long)divisor);
div_count = 1;
continue;
}
divisor_tmp += divisor_tmp;
div_count += div_count;
}
return negetive?0-res:res;
}
// 使用移位进行两数相减
思路:
先将 除数和被除数转换为 long 型的正数
初始 移位 为 1, 同时备份 right
当 被除数 - 除数 向左进行移位的值 < 0 退出,否则移位的数 ++, 算出可以进行移位的最大位数
被除数 - 除数, 向左移位的位数
结果 + 1 相左移动的位数
public int divide2(int dividend, int divisor) {
long right = Math.abs((long)dividend);
long left = Math.abs((long)divisor);
long ans = 0;
while (left<=right){
long k = right,cur = 1;
while (k-(left << cur) > 0) {
cur++;
}
right -= (left << (cur-1));
ans += (1<<(cur-1));
}
if ((dividend^divisor)<0) {
ans = -ans;
}
if(ans >= Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
if(ans <= Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int)ans;
}
// 计算 x 的 n次幂
// 使用 快速幂计算 x 的 n次方
// 主要思路是, 幂次方每次除二,基数每次平方,又因为幂次方每次是奇数偶数交替, ans *= x
public double myPow(double x, int n) {
long m = Math.abs((long)n);
if ((n ^ 1) < 0){
x = 1.0/x;
}
double ans = 1.0;
while (m > 0){
if (m % 2 == 1){
ans *= x;
}
x *= x;
m /= 2;
}
return ans;
}
// 使用二分法在矩阵中查询相应的值
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 left = 0; int right = m-1;
while (left<=right){
int mid = left + (right - left)/2;
if (matrix[mid][0] == target){
return true;
}else if (matrix[mid][0] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}
int lineNum = left - 1 < 0 ? 0: left -1;
left = 0;right = n-1;
while (left<=right){
int mid = left + (right - left)/2;
if (matrix[lineNum][mid] == target){
return true;
}else if (matrix[lineNum][mid] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}
return false;
}
// 相当于进行了展平的操作
// 因为这些数据展平了是,顺序的
public boolean searchMatrix2(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0){
return false;
}
int n = matrix[0].length;
int left = 0; int right = m * n -1;
while (left <= right){
int mid = left + (right - left)/2;
if (matrix[mid/n][mid%n] == target){
return true;
}else if (matrix[mid/n][mid%n] > target){
right = mid -1;
}else {
left = mid + 1;
}
}
return false;
}
// 查询带有重复旋转数组
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0){
return false;
}
int left = 0;int right = nums.length -1;
if (nums[0] == target){
return true;
}else {
while (left < nums.length-1 && nums[left] == nums[0]){
left ++;
}
while (right > 0 && nums[right] == nums[0]){
right --;
}
}
while (left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
return true;
}
if (target >= nums[0]){
if (nums[mid] >= nums[0] && nums[mid] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}else {
if (nums[mid] < nums[0] && nums[mid] > target){
right = mid - 1;
}else {
left = mid + 1;
}
}
}
return false;
}
// 对带有重复元素求解最小值
// 重复数组只要保证数组的前后元素不要一致就可以区分出是否进行了旋转的操作
public int findMin2(int[] nums){
int left = 0,right = nums.length;
while (right - left != 1 && nums[left] == nums[right-1]){
right --;
}
if (nums[left] <= nums[right-1]){
return nums[left];
}
while (left < right){
int mid = left + (right - left)/2;
if (nums[mid] >= nums[0]){
left = mid + 1;
}else {
right = mid;
}
}
return nums[left];
}
// 实现 长度最小的子数组
// 使用双指针实现滑动窗口的解析
先是 递增的加，当 sum 大于期望值 s, 从 left 开始递减，同时更新 最小的长度值
public int minSubArrayLen2(int s, int[] nums)
{
int n = nums.length;
int ans = Integer.MAX_VALUE;
int left = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
while (sum >= s) {
ans = Math.min(ans, i + 1 - left);
sum -= nums[left++];
}
}
return (ans != Integer.MAX_VALUE) ? ans : 0;
}
// 实现求最小的子数组的值
// 主要思想是 首先求出连续的递增和
j ~ i 间的递增和 可以表示为 nums[j] - nums[i] >= s
s + num[i] 可以找到我们想要的 nums[j]
那么就可以求出 j - i 的长度
实现二分搜着找到对应的值，如果没找到多返回一位
public int minSubArrayLen(int s, int[] nums) {
int min = nums.length;
if (min == 0) return 0;
min++;
int[] sums = new int[nums.length + 1];
sums[0] = 0;
for (int i = 1; i <= nums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= nums.length; i++) {
int toFind = s + sums[i - 1];
int bound = binarySearch(sums, toFind);
if (bound > 0) min = Math.min(min, bound - i + 1);
}
return min > nums.length ? 0 : min;
}
private int binarySearch(int[] arr, int key) {
int i = 0;
int j = arr.length - 1;
while (i < j - 1) {
int mid = i + (j - i)/2;
if (arr[mid] < key){
i = mid;
}else if (arr[mid] > key) {
j = mid;
}else {
return mid;
}
}
if (arr[j] >= key){
return j;
}
else{
return -1;
}
}
// 搜索二维矩阵2
从最上方，逆序的对每行进行检测，然后进行二分搜索
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;
for (int i = m-1;i>=0;i--){
if (target >= matrix[i][0] && target <= matrix[i][n-1]){
int index = Arrays.binarySearch(matrix[i], target);
if (index>=0){
return true;
}
}
}
return false;
}
// 搜索二位矩阵2 从左下开始
public boolean searchMatrix(int[][] matrix, int target) {
// 从左下开始， 实际相当于从中间开始
int row = matrix.length-1;
int col = 0;
// 小于的行减，大于的列加
while (row >= 0 && col < matrix[0].length) {
if (matrix[row][col] > target) {
row--;
} else if (matrix[row][col] < target) {
col++;
} else { // found it
return true;
}
}
return false;
}
// h指数，指的是， 最多n篇论文，至少引用 n次
数组是排序的， 只有保证
n - mid = x x 篇论文 ，至少引用 num[x] 次
n - mid <= num[x] 这是正确的答案， 否则我们求最大left = mid + 1;
最后求出的答案一定满足， Math.min(n-left,citations[left]);
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0){
return 0;
}
int n = citations.length;
int left = 0,right = citations.length-1;
while (left < right){
int mid = left + (right - left)/2;
if (n - mid <= citations[mid]){
right = mid;
}else {
left = mid + 1;
}
}
return Math.min(n-left,citations[left]);
}
// 最长的上升子序列
首先看访问当前位置的，是否大于等于0 说明当前位置以及访问过它的最长上升子序列的长度
返回，选或者不选当前元素的最大长度
// 无序数组，找出最长的上升子序列，可以不连续
public int lengthOfLIS(int[] nums) {
int memo[][] = new int[nums.length+1][nums.length];
for (int[] l:memo){
Arrays.fill(l,-1);
}
return lengthOfLIS(nums,-1,0,memo);
}
public int lengthOfLIS(int[] nums, int previndex, int curpos, int[][] memo) {
if (curpos == nums.length) {
return 0;
}
if (memo[previndex + 1][curpos] >= 0) {
return memo[previndex + 1][curpos];
}
int taken = 0;
if (previndex < 0 || nums[curpos] > nums[previndex]) {
taken = 1 + lengthOfLIS(nums, curpos, curpos + 1, memo);
}
int nottaken = lengthOfLIS(nums, previndex, curpos + 1, memo);
memo[previndex + 1][curpos] = Math.max(taken, nottaken);
return memo[previndex + 1][curpos];
}
// 使用动态规划解决 最长上升子序列
记录数组的每一个位置的最长子序列数， 添加新元素是遍历前面找出在小于当前值的情况下，最大的最长子序列数，
当前的最长子序列数，就是前面的加1
public int lengthOfLIS3(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
// 使用二分法，进行 最长上升子序列的测试
// 实际上 就是 找到当前要插入的位置进行替换，如果插入位置在最后则，长度+1进行插入
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == len) {
len++;
}
}
return len;
}
在dp中查询当前数字应该保存的位置，然后进行覆盖，如果插入的位置等于len 就在后面插入 len ++， 最后返回 len
// 使用二分查找 + 插入 计算右侧小于当前元素的个数
从倒数第二个元素开始进行插入， 首先使用二分查找，查找小于当前的元素的最后一个元素， 并记录下标
记录 nums[i] 的 数值， 从 i+1 复制到 i, posit - i , nums[posit] = pivot
public static List<Integer> binaryInsert(int[] nums) {
int n = nums.length;
if (n < 1) {
return new ArrayList<Integer>();
}
Integer[] res = new Integer[n];
res[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
int posit = binarySearch(nums, i + 1, n - 1, nums[i]) - 1;
int pivot = nums[i];
System.arraycopy(nums, i + 1, nums, i, posit - i);
nums[posit] = pivot;
res[i] = posit - i;
}
return Arrays.asList(res);
}
// 这里查找的是，最后一个小于当前元素的位置
private static int binarySearch(int[] nums, int low, int hig, int key) {
while (low <= hig) {
int mid = low + ((hig - low) >> 1);
if (nums[mid] < key) low = mid + 1;
else hig = mid - 1;
}
return low;
}
// 使用归并排序进行计算右侧小于当前元素的个数
public static List<Integer> merge(int[] nums) {
int n = nums.length;
int[] idx = new int[n];
// 使用位置索引，原始位置不变
Integer[] res = new Integer[n];
// 初始化位置索引，还有结果数组
for (int i = 0; i < n; i++) {
idx[i] = i;
res[i] = 0;
}
// 直接使用拷贝，节省拷贝时间
mergeSort(nums, 0, n - 1, idx, idx.clone(), res);
return Arrays.asList(res);
}
// 使用同一的辅助数组，避免频繁创建、销毁
private static void mergeSort(int[] nums, int low, int hig, int[] idx, int[] aux, Integer[] res) {
// 总长
int nRemaining = hig - low + 1;
if (nRemaining < 2) return;
int mid = low + ((hig - low) >> 1);
mergeSort(nums, low, mid, aux, idx, res);
mergeSort(nums, mid + 1, hig, aux, idx, res);
// 如果已经有序，则无需归并。
// 表示 两个数组的左和右进行归并
if (nums[aux[mid]] <= nums[aux[mid + 1]]) {
System.arraycopy(aux, low, idx, low, nRemaining);
return;
}
merge(nums, low, mid, hig, idx, aux, res);
}
private static void merge(int[] nums, int low, int mid, int hig, int[] idx, int[] aux, Integer[] res) {
int i = low, j = mid + 1;
for (int k = low; k <= hig; k++) {
if (i > mid) {
idx[k] = aux[j++];
} else if (j > hig) {
// 这里
res[aux[i]] += j - mid - 1;
idx[k] = aux[i++];
} else if (nums[aux[i]] > nums[aux[j]]) {
// 如果统计的是总交换次数，那么应该在这里+mid-i+1
idx[k] = aux[j++];
} else {
// 这里
res[aux[i]] += j - mid - 1;
idx[k] = aux[i++];
}
}
}
// 使用模拟 + 二分查找 找寻右侧小于当前元素的个数
创建一个数组用于存储要排序， 创建结果数组 res
从后向前遍历，在排序数组中查找要插入的位置，（数组从小到大排序）
那么这个位置，就是其比右边大的数据个数
同时我们将我们的数插入到对应的位置
这里结果数组必须使用 Integer 因为，我们可能初始添加最后一个元素
// 使用新的 二分查找
public List<Integer> countSmaller(int[] nums) {
//排序数组
List<Integer> temp = new ArrayList<>();
//结果数组
Integer[] res = new Integer[nums.length];
//原数组从后向前遍历，根据二分法升序插入到新数组
for(int i=nums.length-1;i>=0;i--){
int left = 0,right = temp.size();
while(left<right){
int mid =left+(right-left)/2;
if(temp.get(mid)>=nums[i]){
right = mid;
}else{
left = mid+1;
}
}
//新数组对应位置的下标即为原数组右侧小于该数的个数
res[i] = left;
temp.add(left,nums[i]);
}
return Arrays.asList(res);
}
// 区间和的个数
这里一定要主要可能会出现区间和超过整数的范围，所以保存和一定用long类型
public int countRangeSum2(int[] nums,int lower,int upper){
int n = nums.length;
long presum = 0;
// 这里必须 n + 1 要保证 第一个和等于0
long[] S = new long[n+1];
int ret = 0;
for (int i=1;i<=n;i++){
presum += nums[i-1];
for (int j=1;j<=i;j++){
if (lower <= presum -S[j-1] && presum - S[j-1] <= upper){
ret ++;
}
}
S[i] = presum;
}
return ret;
}
// 使用归并排序进行计算
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
vector<int64_t> S(n+1,0);
vector<int64_t> assist(n+1,0);
for(int i=1;i<=n;i++)S[i] = S[i-1] + nums[i-1];
return merge(S,assist,0,n,lower,upper);
}
int merge(vector<int64_t> &S,vector<int64_t> &assist,int L,int R,int low,int up){
if(L >= R) return 0;
int cnt = 0;
int M = L + (R-L)/2;
cnt += merge(S,assist,L,M,low,up);
cnt += merge(S,assist,M+1,R,low,up);
int Left = L;
int Upper = M+1,Lower = M+1;
while(Left <= M){
while(Lower <= R && S[Lower] - S[Left] < low)Lower++;
while(Upper <= R && S[Upper] - S[Left] <= up)Upper++;
cnt += Upper - Lower;
Left++;
}
//以下为归并排序中归并过程
Left = L;
int Right = M + 1;
int pos = L;
while(Left<= M || Right <= R){
if(Left > M)assist[pos] = S[Right++];
if(Right > R && Left <= M)assist[pos] = S[Left++];
if(Left <= M && Right <= R){
if(S[Left] <= S[Right])assist[pos] = S[Left++];
else assist[pos] = S[Right++];
}
pos++;
}
for(int i=L;i<=R;i++)S[i] = assist[i];
return cnt;
}
// 俄罗斯套娃
降维 + 最长递增子序列
首先对一个序列进行排序，然后另一维数组就转换为最长的递增子序列的值
不排序，整体的二维数组是无序的
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按宽度升序排列，如果宽度一样，则按高度降序排列
Arrays.sort(envelopes, new Comparator<int[]>()
{
@Override
public int compare(int[] a, int[] b) {
return a[0] == b[0] ?
b[1] - a[1] : a[0] - b[0];
}
});
// 对高度数组寻找 LIS
int[] height = new int[n];
for (int i = 0; i < n; i++)
height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
// 最大的矩阵和
在计算当前位置的矩阵和的时候，就是让 上 面的矩阵和加上 左边的矩阵和 - 左上角重叠矩阵和 ，其次要算每一个矩阵 就是让 sum[i][j] - sum[i][k] sum[i][j] - sum[k][j]
int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length, res = Integer.MIN_VALUE;
int[][] sum = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int t = matrix[i][j];
if (i > 0) t += sum[i - 1][j];
if (j > 0) t += sum[i][j - 1];
if (i > 0 && j > 0) t -= sum[i - 1][j - 1];
sum[i][j] = t;
for (int r = 0; r <= i; ++r) {
for (int c = 0; c <= j; ++c) {
int d = sum[i][j];
if (r > 0) d -= sum[r - 1][j];
if (c > 0) d -= sum[i][c - 1];
if (r > 0 && c > 0) d += sum[r - 1][c - 1];
if (d <= k) res = Math.max(res, d);
}
}
}
}
return res;
}
// 使用二分法进行 矩阵中的第k小
// 可以确定左下角最小， 右上角最大
使用二分法进行判断中间值， 统计小于当前数的数量，
统计时可以先判断每行或每列的最后一位，如果大，则整列都符合条件
不是找到满足条件的就返回，而是继续二分
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int left = matrix[0][0];
int right = matrix[m-1][n-1];
while (left < right){
int mid = left + (right - left)/2;
int countLeMid = countLeMid(matrix, mid, m, n);
if (countLeMid < k){
left = mid + 1;
}else {
right = mid;
}
}
return left;
}
private int countLeMid(int[][] matrix, int mid, int m, int n) {
int res = 0;
int j = n - 1;
int i = 0;
while (i<m){
if (matrix[i][j] <= mid){
// j的最后坐标 j ，但是最后有 j + 1 个元素
res += (j + 1);
i++;
}else {
j--;
}
}
return res;
}
证明如下：
设min^{t}为第t轮二分的min，mid^{t}为第t轮二分的mid,max^{t}为第t轮二分的max,target是我们要查找的值。
因此min^{t}=min^{t-1}或者min^{t}=mid^{t-1}+1。如果min^{t}=mid^{t-1}+1,说明小于等于mid^{t-1}的矩阵中元素的个数小于k,说明mid^{t-1}<target,那么min^{t}=mid^{t-1}+1<target+1,即min^{t}<=target。因此，只要其中有一次的min是由上一轮的mid转化而来的，那么就可以保证min始终<=target。如果min一直保持着初始状态，从来没有从上一轮mid转化而来过，那么min^{t}=min{1}<=target。因此，min始终小于等于target。
同时，max^{t}=mid^{t-1}或者max^{t}=max^{t-1}。如果max^{t}=mid^{t-1},说明小于等于mid^{t-1}的矩阵中的元素的个数>=k，说明mid^{t-1}>=target。因此，只要其中有一次的max是由上一轮的mid转化而来的，那么就可以保证max始终>=target。如果max一直保持着初始状态，从来没有从上一轮mid转化而来过，那么max^{t}=max{1}>=target。因此，max始终大于等于target。
此外，由于min和max构成的区间是在不断缩小的，所以最终肯定可以达到min=max的状态，从而退出循环。此时，由于min<=target,max>=target,而min=max，所以min=max=target。
得证。
// 判断一个字符串是不是另一个字符串的子序列
String 的 indexOf 可以获取 单个字符在 String 中的位置 indexOf(c,i) 可以从i开始获取之后字符的位置，如果
public boolean isSubsequence(String s, String t) {
int index = 0,i = 0;
while(index < s.length() && t.indexOf(s.charAt(index),i) >= i){
i = t.indexOf(s.charAt(index),i) + 1;
index++;
}
return index == s.length();
}
// 二分查询 最右区间
使用 hashmap 保存 区间的具体位置，然后根据二分查找最小的可能值，然后去map中找到具体的下标
public int[] binary_search(int[][] intervals, int target, int start, int end) {
if (start >= end) {
if (intervals[start][0] >= target) {
return intervals[start];
}
return null;
}
int mid = (start + end) / 2;
if (intervals[mid][0] < target) {
return binary_search(intervals, target, mid + 1, end);
} else {
return binary_search(intervals, target, start, mid);
}
}
public int[] findRightInterval(int[][] intervals) {
int[] res = new int[intervals.length];
HashMap<int[], Integer> hash = new HashMap<>();
for (int i = 0; i < intervals.length; i++) {
hash.put(intervals[i], i);
}
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 0; i < intervals.length; i++) {
int[] interval = binary_search(intervals, intervals[i][1], 0, intervals.length - 1);
res[hash.get(intervals[i])] = interval == null ? -1 : hash.get(interval);
}
return res;
}
// 排列硬币
根据数学公式，k(k+1) /2 = n，可以得到其正数解为：k = sqrt(2n+1/4) - 1/2。然后求整即可。
唯一的问题是，这里2n+1/4有可能会超出sqrt函数的参数范围。
于是，我们可以变换一下， k = sqrt(2) * sqrt(n+1/8) - 1/2，这样求平方根就不会超限了。
于是，我们就有了这么一行代码
class Solution {
public int arrangeCoins(int n) {
return (int)(Math.sqrt(2) * Math.sqrt(n + 0.125) - 0.5);
}
}
// 使用二分法检测排列硬币的问题
public int arrangeCoins(int n) {
if (n == 0){
return 0;
}
int left = 1, right = n/2 + 1;
while (left < right){
int mid = left + (right - left+1)/2;
if (sumBeforeMid(mid) <= n){
left = mid;
}else {
right = mid - 1;
}
}
return right;
}
public long sumBeforeMid(long x){
if (x > 0){
if (x % 2 == 0){
return (x/2) *(x + 1);
}else {
return x * (x-1)/2 + x;
}
}
return 0;
}
// 查找 供暖器需要的半径
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int j = 0;
int max = -1;
for(int i = 0;i < houses.length;i++){
if((j + 1 < heaters.length) && (Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1]))){
j++;
i--;
}else{
if(max < Math.abs(houses[i] - heaters[j])){
max = Math.abs(houses[i] - heaters[j]);
}
}
}
return max;
}
