#

二分

lc35. 搜索插入位置中等hot

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    while(left <= right) {
        const mid = Math.floor((left + right) / 2);
        if(nums[mid] === target) {
            return mid
        } else if(nums[mid] < target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return left;
};

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 次得到输入数组。

示例 2：

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

示例 3：

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

思路

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

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

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
};

时间复杂度: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

示例 2：

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

示例 3：

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

思路还是二分法

初始化 left = 0, right = nums.length - 1

当 left <= right 时执行以下循环：

• 计算中间值 mid = (left + right) // 2
• 如果 nums[mid] == target，直接返回 mid
• 判断哪一边是有序的：
  • 如果 nums[left] <= nums[mid]，说明左半部分是有序的
    • 判断 target 是否在左边范围内：
      • 是：right = mid - 1
      • 否：left = mid + 1
  • 否则，右半部分是有序的
    • 判断 target 是否在右边范围内：
      • 是：left = mid + 1
      • 否：right = mid - 1

如果循环结束仍没找到，返回 -1

function search(nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) return mid;

    // 左半边有序
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    // 右半边有序
    else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

时间复杂度: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

示例 2：

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

思路

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

只需要额外判断一个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
};

时间复杂度: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]

示例 2：

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

示例 3：

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

思路

看到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]
};

时间复杂度: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

示例 2：

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

示例 3：

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

思路

还是一个标准的二分

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
}

lc162. 寻找峰值中等hot

题目描述

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

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

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

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

示例 1：

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

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

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;
};

时间复杂度:O(logn)

空间复杂度:O(1)

lc287. 寻找重复数中等

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

思路：二分法

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

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

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

var findDuplicate = function(nums) {
  let left = 1;
  let right = nums.length - 1; // 因为 nums 是 n+1 个数，值域是 [1, n]

  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    // 统计数组中小于等于 mid 的个数
    let count = 0;
    for (let num of nums) {
      if (num <= mid) count++;
    }

    if (count > mid) {
      // 说明重复的数在 [left, mid]
      right = mid;
    } else {
      // 说明重复的数在 [mid+1, right]
      left = mid + 1;
    }
  }

  // left == right 时就是那个重复的数
  return left;
};

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

空间复杂度:O(1)

快慢指针

数组中每个值 nums[i] 都在 [1, n] 范围内，所以你可以把它当成“下一跳”：

把每个数组元素看成一个“节点”，值是“下一跳的指针”：

0 → nums[0]=3
3 → nums[3]=4
4 → nums[4]=2
2 → nums[2]=3
3 → 4 → 2 → 3... （形成了环）

因为有重复的值，所以会有至少两个下标指向同一个位置，这个就等价于链表中有环！

var findDuplicate = function(nums) {
  let slow = nums[0];
  let fast = nums[0];

  // 先走一步，进入循环前确保 fast 和 slow 已经动了
  slow = nums[slow];
  fast = nums[nums[fast]];

  while (slow !== fast) {
    // 快慢指针第一次相遇（在环里）
    slow = nums[slow];
    fast = nums[nums[fast]];
  }

  // 令 ptr1 = nums[0]，ptr2 = 相遇点，然后都每次走一步：
  // 找到入口
  let p1 = nums[0];
  let p2 = slow;
  while (p1 !== p2) {
    p1 = nums[p1];
    p2 = nums[p2];
  }

  return p1;
};

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 。

示例 2：

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

示例 3：

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

思路：动态规划

定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。

状态转移方程：

dp[i] = max(dp[j] + 1) 其中 j < i 且 nums[j] < nums[i]

初始化：每个位置最少都是1（自己本身）：

dp[i] = 1

最后答案是：max(dp)

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);
};

时间复杂度：O(n^2)，其中 n 为数组 nums 的长度。

动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态

所以总时间复杂度为 O(n^2)

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

思路二：二分+贪心

用一个数组 sub 维护当前的最小结尾元素。

遍历每个 num：

• 如果 num 比 sub 最后一个大，就可以扩展子序列：sub.push(num)
• 否则，用 二分查找 替换掉第一个 ≥ num 的元素（将来留更多扩展空间），保持 sub 的最小递增结构。

function lengthOfLIS(nums) {
  const sub = [];

  for (const num of nums) {
    let left = 0, right = sub.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (sub[mid] < num) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    if (left < sub.length) {
      sub[left] = num;
    } else {
      sub.push(num);
    }
  }

  return sub.length;
}

时间复杂度: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

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

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
};

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

题目描述

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

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

示例 1：

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

示例 2：

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

二分

我们要在两个有序数组中找第 k 小的数。中位数是特定的第 k 小的数：

• 偶数个数：中位数是第 k = (m+n)/2 和 k+1 小数的平均。
• 奇数个数：中位数是第 k = (m+n+1)/2 小的数。

var findMedianSortedArrays = function(nums1, nums2) {
  const m = nums1.length, n = nums2.length;

  // 找两个有序数组中的第 k 小的数
  const getKth = (a, b, k) => {
    let indexA = 0, indexB = 0;

    while (true) {
      // 边界情况
      if (indexA === a.length) return b[indexB + k - 1];
      if (indexB === b.length) return a[indexA + k - 1];
      if (k === 1) return Math.min(a[indexA], b[indexB]);

      // 正常二分流程
      let half = Math.floor(k / 2);
      let newIndexA = Math.min(indexA + half, a.length) - 1;
      let newIndexB = Math.min(indexB + half, b.length) - 1;
      let pivotA = a[newIndexA], pivotB = b[newIndexB];

      if (pivotA <= pivotB) {
        k -= (newIndexA - indexA + 1);
        indexA = newIndexA + 1;
      } else {
        k -= (newIndexB - indexB + 1);
        indexB = newIndexB + 1;
      }
    }
  };

  const totalLength = m + n;
  if (totalLength % 2 === 1) {
    return getKth(nums1, nums2, Math.floor(totalLength / 2) + 1);
  } else {
    const mid1 = getKth(nums1, nums2, totalLength / 2);
    const mid2 = getKth(nums1, nums2, totalLength / 2 + 1);
    return (mid1 + mid2) / 2;
  }
};

时间复杂度：O(log(min(m, n)))，因为每次都砍掉 k/2，递归 log 级别。

空间复杂度：O(1)，因为是迭代写法（递归写法是 O(log n)）。

lc74. 搜索二维矩阵中等hot

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

二分

function searchMatrix(matrix: number[][], target: number): boolean {
  const m = matrix.length;
  const n = matrix[0].length;

  let left = 0, right = m * n - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const row = Math.floor(mid / n);
    const col = mid % n;
    const midValue = matrix[row][col];

    if (midValue === target) {
      return true;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

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。

时间复杂度:O(mn)

空间复杂度：O(1)

对每一行用二分

function searchMatrix(matrix: number[][], target: number): boolean {
  for (const row of matrix) {
    let left = 0, right = row.length - 1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (row[mid] === target) return true;
      else if (row[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
  }
  return false;
}

时间复杂度:O(mlogn)

空间复杂度：O(1)

从右上角开始走

function searchMatrix(matrix: number[][], target: number): boolean {
  if (!matrix.length || !matrix[0].length) return false;

  const rows = matrix.length;
  const cols = matrix[0].length;

  let i = 0;        // 从第一行
  let j = cols - 1; // 从最后一列开始

  while (i < rows && j >= 0) {
    const val = matrix[i][j];
    if (val === target) {
      return true;
    } else if (val > target) {
      j--; // 向左移动
    } else {
      i++; // 向下移动
    }
  }

  return false;
}

时间复杂度：

• 最坏 O(m + n)，其中 m 是行数，n 是列数。
• 每次移动一格（左或下），最多走 m + n 步。

空间复杂度：

• O(1)，原地搜索。