小宋爱睡觉
  • 数组
Crucials
2022-02-07

二分

#

# 二分

# lc153. 寻找旋转排序数组中的最小值中等hot

题目描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
1
2
3

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
1
2
3

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
1
2
3

思路

常规做法一般是一次遍历判断前一个数是否大于后一个数

采用二分可以降低时间复杂度

var findMin = function(nums) {
  if(!nums.length) return null
  if(nums.length === 1) return nums[0]
  let left = 0, right = nums.length - 1, mid
  if(nums[right] > nums[left]) return nums[left]
  while(left <= right) {
    mid = Math.floor(left + (right - left) / 2)
    if(nums[mid] >  nums[mid + 1]) return nums[mid + 1]
    if(nums[mid] < nums[mid - 1]) return nums[mid]
    if(nums[mid] < nums[left]) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return null
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度:O(logn)

空间复杂度:O(1)

# lc33. 搜索旋转排序数组中等hot

题目描述

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
1
2

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
1
2

示例 3：

输入：nums = [1], target = 0
输出：-1
1
2

思路还是二分法

var search = function(nums, target) {
  if(!nums.length) return -1
  let left = 0, right = nums.length - 1, mid
  while(left <= right) {
    mid = Math.floor(left + (right - left) / 2)
    if(nums[mid] === target) {
      return mid
    }
    if(nums[mid] >= nums[left]) {
      if(target >= nums[left] && target < nums[mid]) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else {
      if(target > nums[mid] && target <= nums[right]) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }
  return -1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度:O(logn)

空间复杂度:O(1)

# lc81. 搜索旋转排序数组 II 中等

题目描述

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
1
2

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
1
2

思路

和上一题不同的是他增加了重复的值

只需要额外判断一个mid的值是否和left的值相同，相同的话就left往后移一位即可

var search = function(nums, target) {
  if(!nums.length) return false
  let left = 0, right = nums.length - 1, mid
  while(left <= right) {
    mid = Math.floor(left + (right - left) / 2)
    if(nums[mid] === target) {
      return true
    }
    if(nums[mid] === nums[left]) {
      left++
      continue
    }
    if(nums[mid] >= nums[left]) {
      if(target >= nums[left] && target < nums[mid]) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else {
      if(target > nums[mid] && target <= nums[right]) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }
  return false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度:O(logn)

空间复杂度:O(1)

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

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
1
2

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
1
2

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]
1
2

思路

看到logn时间复杂度肯定会想起二分

var searchRange = function(nums, target) {
  let left = 0, right = nums.length - 1, mid
  while(left <= right) {
    mid = Math.floor(left + (right - left) / 2)
    if(nums[mid] === target) {
      left = mid - 1
      right = mid + 1
      while(true) {
        if(nums[left] === target) left--
        else if(nums[right] === target) right++
        else {
          return [left + 1, right - 1]
        }
      }
    }
    if(nums[mid] > target) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return [-1, -1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度:O(logn)

空间复杂度:O(1)

# lc875. 爱吃香蕉的珂珂中等

题目描述

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4
1
2

示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30
1
2

示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23
1
2

思路

还是一个标准的二分

var minEatingSpeed = function(piles, h) {
  let left = 1, right = Math.max(...piles), mid
  while(left <= right) {
    mid = Math.floor(left + (right - left) / 2)
    if(canFinish(mid, piles, h)) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return left
};
function canFinish(mid, piles, h) {
  let sum = 0
  for(let i = 0; i < piles.length; i++) {
    sum += Math.ceil(piles[i] / mid)
    if(sum > h) return false
  }
  return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# lc162. 寻找峰值中等hot

题目描述

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
1
2
3

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。
1
2
3
4
var findPeakElement = function(nums) {
    let left = 0, right = nums.length-1;
    while(left < right){
        let mid = Math.floor(left + (right - left) / 2) + 1;
        if(nums[mid-1] > nums[mid]) right = mid - 1;
        else left = mid;
    }
    return left;
};
1
2
3
4
5
6
7
8
9

时间复杂度:O(logn)

空间复杂度:O(1)

# lc287. 寻找重复数中等

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2
1
2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3
1
2

示例 3：

输入：nums = [1,1]
输出：1
1
2

示例 4：

输入：nums = [1,1,2]
输出：1
1
2

思路：二分法

以1，4，3，2，2为例

  • <=1 有1个
  • <=2 有3个
  • <=3 有4个
  • <=4 有5个

可以发现，在重复的数字之后<=i的都有i + 1个,而在重复数字之前的都有i个

var findDuplicate = function(nums) {
 let l = 0, r = nums.length - 1;
  while(l <= r){
    let mid = Math.floor(l + (r - l) / 2);
    let cnt = 0;
    for(let num of nums){
        if(num <= mid) cnt++;
    }
    if(cnt <= mid) l = mid + 1;
    else r = mid - 1;
  }
  return l;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度:O(nlogn) 其中 n为 nums 数组的长度。二分查找最多需要二分 O(logn) 次，每次判断的时候需要O(n) 遍历 nums 数组求解小于等于 mid 的数的个数，因此总时间复杂度为 O(nlogn)

空间复杂度:O(1)

# lc300. 最长递增子序列中等hot

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
1
2
3

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
1
2

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1
1
2

思路：动态规划

如果nums[i]比前面的某个nums[j]更大，那么就有2个可能（还是本来的dp[i]最大 or dp[j] + 1更大），选择更大的作为结果 dp[i] = Math.max(dp[i], dp[j] + 1)

var lengthOfLIS = function (nums) {
    let dp = Array(nums.length).fill(1);
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp);
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(n^2)，其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n^2)

空间复杂度：O(n)，需要额外使用长度为 n 的 dp 数组

思路二：二分+贪心

创建一个dp数组，进循环，假如nums[i + 1]比nums[i]大，那么直接追加到后面即可

否则进入二分

  • 在dp数组(是有序的)里面用二分
  • 找到比nums[i]大，但尽可能小的值，然后替换
  • 这样的话，就可以保证他可以在他后面接更大的数字
var lengthOfLIS = function (nums) {
  const n = nums.length;
  let len = 1;
  if (n == 0) return 0;
  const dp = new Array(n + 1);
  dp[len] = nums[0];
  for (let i = 1; i < n; i++) {
    if (nums[i] > dp[len]) dp[++len] = nums[i];
    else {
      let l = 1,
        r = len;
      while (l <= r) {
        let mid = Math.floor((r - l) / 2) + l;
        if (dp[mid] < nums[i]) {
          l = mid + 1;
        } else {
          r = mid - 1;
        }
      }
      dp[l] = nums[i];
    }
  }
  return len;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度:O(nlogn) 数组nums 的长度为 n，我们依次用数组中的元素去更新 dp 数组，而更新dp数组时需要进行 O(logn) 的二分搜索，所以总时间复杂度为 O(nlogn)

空间复杂度:O(n)

# lc69. x 的平方根 简单hot

题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
1
2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
1
2
3
var mySqrt = function(x) {
  if(x < 2) return x
  let left = 1
  let right = Math.floor(x / 2)
  let mid 
  while(left <= right) {
    mid = Math.floor(left + (right - left) / 2)
    if(mid * mid === x) return mid
    if(mid * mid < x) left = mid + 1
    else right = mid - 1
  }
  return right
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# lc4. 寻找两个正序数组的中位数困难hot

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
1
2
3

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
1
2
3

二分

var findMedianSortedArrays = function (nums1, nums2) {
  // 找到合适的分割线
  if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
  let m = nums1.length,
    n = nums2.length,
    totalLeft = Math.ceil((m + n) / 2);

  let l = 0,
    r = m;
  while (l < r) {
    // 找到短的数组的中间值
    let i = Math.ceil((l + r) / 2);
    // 总长度的一半剪掉中间值
    let j = totalLeft - i;
    if (nums1[i - 1] > nums2[j]) {
      r = i - 1;
    } else {
      l = i;
    }
  }

  let i = l,
    j = totalLeft - i; // 找到该分割线的下标
  // 短的数组全小于长的数组 
  let l1 = i == 0 ? -Infinity : nums1[i - 1];
  // 长的数组全小于短的数组
  l2 = j == 0 ? -Infinity : nums2[j - 1];
  // 刚好在最短的最后面
  r1 = i == m ? Infinity : nums1[i];
  // 刚好在最长的最后面
  r2 = j == n ? Infinity : nums2[j];

  return (m + n) & 1
    ? Math.max(l1, l2)
    : (Math.max(l1, l2) + Math.min(r1, r2)) / 2;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度:O(log(m + n))

空间复杂度：O(1)

# lc240. 二维数组中的查找/搜索二维矩阵 II中等hot

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。
1
2
3
4
5
6
7
8
9
10
11
12

思路一：直接暴力

暴力的话就是二维数组遍历，没什么好说的

思路二：螃蟹走法

这张图一目了然，或者也可以从右上角开始遍历

var findNumberIn2DArray = function(matrix, target) {
    if(!matrix.length || !matrix[0].length) return false
    let i = matrix.length - 1, j = 0
    while(i >= 0 && j < matrix[0].length) {
        if(matrix[i][j] === target) return true
        else if(matrix[i][j] > target) {
            i--
        } else {
            j++
        }
    }
    return false
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度:O(mn)

空间复杂度：O(1)

二分

var searchMatrix = function(matrix, target) {
  for (const row of matrix) {
    const index = search(row, target);
    if (index >= 0) {
      return true;
    }
  }
  return false;
};

const search = (nums, target) => {
  let low = 0, high = nums.length - 1;
  while (low <= high) {
    const mid = Math.floor((high - low) / 2) + low;
    const num = nums[mid];
    if (num === target) {
      return mid;
    } else if (num > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度:O(mlogn)

空间复杂度：O(1)

上次更新: 2022/03/21, 11:27:08
回溯
有关区间

← 有关区间→

Copyright © 2021-2022 粤ICP备2021165371号