算法长征（4）查找算法

发表于 更新于 分类于 ， 阅读次数： 本文字数： 8.8k 阅读时长 ≈ 16 分钟

查找算法

bisect 文档:https://docs.python.org/zh-cn/3.6/library/bisect.html

  • 二分查找求左边界 第一个 False : 不小于target的第一个数

1
2
3
4
5
6
7
8
9
def leftMargin(): # 左边界
   left, right = 0, len(nums) - 1
	while left <= right:
       mid = (left + right) // 2
       if nums[mid] < target: # ... Ture # False ...
          left = mid + 1
       else:
          right = mid - 1
   return left if nums[left] == target else -1 # 越界检验

  • 二分查找右边界 [第一个 True ]

1
2
3
4
5
6
7
8
9
def rightMargin(): # 右边界
		left, right = 0, len(nums) - 1
    while left <= right:
    		mid = (left + right) // 2
        if nums[mid] > target: # ... False # Ture ...
           right = mid - 1
        else:
           left = mid + 1
    return right if nums[right] == target else -1

找出数组中重复的数字。==在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内==。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

  • 哈希表 / Set、原地交换（空间0（1））
  • 合理利用 val 和 key 的关系
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findRepeatNumber(self, nums: [int]) -> int:
        dic = set()
        for num in nums:
            if num in dic: return num
            dic.add(num)
        return -1
		def findRepeatNumber(self, nums: [int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i:
                i += 1
                continue
            if nums[nums[i]] == nums[i]: 
              	return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1

统计一个数字在排序数组中出现的次数。

  • 找到目标值「最后」出现的分割点，并「往前」进行统计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        # 求右边界
        while left <= right:
            mid = (right + left) // 2
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        # 最后要检查 right 越界的情况
        if right < 0 or nums[right] != target:
            return 0
        ans = 0
        while right >= 0 and nums[right] == target :
            right -= 1
            ans += 1
        return ans

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

  • 排序数组中的搜索问题，首先想到 二分法 解决。
    • 根据题意，数组可以按照以下规则划分为两部分
      • 左子数组： nums[i] = i
      • 右子数组： nums[i]  = i
  • 缺失的数字等于 “右子数组的首位元素” 对应的索引；因此考虑使用二分法查找 “右子数组的首位元素” 。

Picture1.png

1
2
3
4
5
6
7
8
9
10
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == m: 
              	i = m + 1
            else: 
              	j = m - 1
        return i

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

  • 我们将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树

Picture1.png

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        i, j = len(matrix) - 1, 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target: 
              	i -= 1
            elif matrix[i][j] < target: 
              	j += 1
            else: 
              	return True
        return False

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

  • 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        # 无法判断左右， right -= 1 缩小范围
        left, right = 0, len(numbers) - 1
        while left < right:
            mid = left + (right - left) // 2
            if numbers[mid] < numbers[right]:
                right = mid
            elif numbers[mid] > numbers[right]:
                left = mid + 1
            else:
                right -= 1
        return numbers[left]

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

  • 哈希表存储频数、索引
1
2
3
4
5
6
7
class Solution:
    def firstUniqChar(self, s: str) -> str:
        frequency = collections.Counter(s)
        for i, ch in enumerate(s):
            if frequency[ch] == 1:
                return ch
        return ' '
  • 队列：使用了「延迟删除」这一技巧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def firstUniqChar(self, s: str) -> str:
        position = dict()
        q = collections.deque()
        n = len(s)
        for i, ch in enumerate(s):
            if ch not in position:
                position[ch] = i
                q.append((s[i], i))
            else:
                position[ch] = -1
                while q and position[q[0][0]] == -1:
                    q.popleft()
        return ' ' if not q else q[0][0]

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

  • from sortedcontainers import SortedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def reversePairs(self, nums):
        # 逆序 + 二分插入
        import bisect
        res = 0
        q = []
        n = len(nums)
        for i in range(n-1,-1,-1):
            s = nums[i]
            j = bisect.bisect_left(q, s)
            res += j
            q[j:j] = [s] 
        return res
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)       
        sl = SortedList()
        ans = 0
        for i in range(n-1, -1, -1):        # 反向遍历
            cnt = sl.bisect_left(nums[i])   # 找到右边比当前值小的元素个数
            ans += cnt                      # 记入答案
            sl.add(nums[i])                 # 将当前值加入有序数组中
        
        return ans

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

  • 二分查找、双指针
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
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 二分查找
        n = len(numbers)
        for i in range(n):
            left, right = i + 1, n - 1
            while left <= right:
                mid = (left + right) // 2
                if numbers[mid] == target - numbers[i]:
                    return [i + 1, mid + 1]
                elif numbers[mid] > target - numbers[i]:
                    right = mid - 1
                else:
                    left = mid + 1
        return [-1, -1] 
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 双指针
        low, high = 0, len(numbers) - 1
        while low < high:
            total = numbers[low] + numbers[high]
            if total == target:
                return [low + 1, high + 1]
            elif total < target:
                low += 1
            else:
                high -= 1
        return [-1, -1]

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

  • 排序 + 双指针 + 去重
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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 排序 + 双指针 + 去冲
        n = len(nums)
        nums.sort()
        ans = []
        for i in range(n):
            if nums[i] > 0: # 剪枝加速
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i + 1, n - 1
            while left < right:
                cur = nums[i] + nums[left] + nums[right]
                if cur == 0:
                    ans.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    right -= 1
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    left += 1
                elif cur > 0:
                    right -= 1
                else:
                    left += 1
        return ans

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

  • 前缀和 + 二分查找 o(nlogn)、滑动窗口o(n)【连续，正整数】
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
37
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 【前缀和 + 二分查找 o(nlogn)】
        if sum(nums) < target:
            return 0
        n = len(nums)
        pre = list(accumulate([0] + nums)) # itertools.accumulate()
        ans = n + 1
        for i in range(n + 1):
            cur = target + pre[i]
            """
            left = bisect.bisect_left(pre, cur)
            """ 
            left = i + 1
            right = n
            while left <= right:
                mid = (left + right) // 2
                if pre[mid] < cur:
                    left = mid + 1
                else:
                    right = mid - 1
            if left != n+1: 
                ans = min(ans, left - i)
        return ans 
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if sum(nums) < target:
            return 0
        cur, res = 0, len(nums) + 1
        i = 0
        for j, var in enumerate(nums):
            cur += var
            while i <= j and cur >= target:
                if (t:= j - i + 1) < res:
                    res = t 
                cur -= nums[i]
                i += 1
        return res

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

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
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 前缀和单调 + 二分查找
        if k == 0:
            return 0
        k = math.log(k)
        pre = [0]
        for num in nums:
            pre.append(pre[-1] + math.log(num))
        cur = res =  0
        for i in range(1, len(pre)):
            cur = k + pre[i - 1]
            j = bisect.bisect_left(pre, cur, lo = i)
            res += j - i 
        return res
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 滑动窗口
        n = len(nums)
        left, right = 0, n - 1
        res = 0
        i, cur =0,  1
        for j, num in enumerate(nums):
            cur *= num
            while i <= j and cur >= k: # 左跟着右
                cur //= nums[i]
                i += 1
            res += j - i + 1
        return res

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

  • 二分查找 o(logN)

利用按位异或的性质，可以得到mid 和相邻的数之间的如下关系，其中 ⊕ 是按位异或运算符：

  • 当mid 是偶数时，mid+1=mid⊕1；

  • 当mid 是奇数时，mid−1=mid⊕1。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) // 2
            if nums[mid] == nums[mid ^ 1]:
                low = mid + 1
            else:
                high = mid
        return nums[low]

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

1
2
3
4
5
6
7
8
class Solution:
    def __init__(self, w: List[int]):
        self.pre = list(accumulate(w))
        self.total = sum(w)
    def pickIndex(self) -> int:
        # 前缀和 + 二分查找
        r = random.randint(1, self.total)
        return bisect_left(self.pre, r)

狒狒喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。狒狒可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = max(1, sum(piles) // h), max(piles)
        def check(k):
            count = 0
            for pile in piles:
                count += ceil(pile / k)
            return count > h
        while left <= right: 
            mid = (left + right) // 2
            if check(mid): # ... Ture # False(r) ...
                left = mid + 1
            else:
                right = mid - 1
        return left

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 输出：13 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

  • 优先队列：这个矩阵的每一行均为一个有序数组。问题即转化为从这 nn 个有序数组中找第 kk 大的数，可以想到利用归并排序的做法，归并到第 kk 个数即可停止。需要用小根堆维护，以优化时间复杂度。
  • 二分查找
    • 初始位置在 matrix [n - 1] [0]（即左下角）；
    • 设当前位置为 matrix [i] [j]。若 matrix [i] [j] ≤mid，则将当前所在列的不大于 mid 的数的数量（即 i + 1i+1）累加到答案中，并向右移动，否则向上移动；
    • 可以线性计算对于任意一个 mid，矩阵中有多少数不大于它。这满足了二分查找的性质。
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
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # 优先队列
        n = len(matrix)
        heap = [(matrix[i][0], i, 0) for i in range(n)]
        heapq.heapify(heap)
        res = 0
        for i in range(k - 1):
            num, x, y = heapq.heappop(heap)
            if y != n - 1:
                heapq.heappush(heap, (matrix[x][y + 1], x, y + 1))
        return heap[0][0]
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # 二分查找
        n = len(matrix)
        def check(mid):
            i, j = n - 1, 0
            num = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    num += i + 1
                    j += 1
                else:
                    i -= 1
            return num < k 
        # 【第一个False】
        left, right = matrix[0][0], matrix[-1][-1]
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return left