日拱两卒（一）

Leetcode的考察点和ACM不太一样，之前面试也有几次尴尬写不出的经历。

从2026.07.04开始把Hot100过一遍，因为前面几题其实很久以前提交过，所以这次倒着刷。

这轮试着用Python而不是C++！

50天！每天两题写完差不多正好是9月日常实习。

100#

有n + 1个整数，值域是[1, n]，找出唯一的重复的数。

假设这个重复的数是x。定义cnt[i]为小于等于i的数的个数。

cnt[i] <= i 当 i <= x - 1时。

cnt[i] > i 当 i >= x 时。

所以二分出最小的满足cnt[i] > i的i就可以了。

1
class Solution:
2
    def findDuplicate(self, nums: List[int]) -> int:
3
        l = 1
4
        r = len(nums) - 1
5
        while l < r:
6
            mid = (l + r) >> 1;
7

8
            cnt = 0
9
            for num in nums:
10
                cnt += num <= mid
11

12
            if cnt > mid:
13
                r = mid
14
            else:
15
                l = mid + 1
16

17
        return l

99#

按字典序找出下一个排列。

比如[1, 2, 3]的下一个是[1, 3, 2]，再下一个是[2, 1, 3]。

[1, 3, 5, 4, 2] -> [1, 4, 5, 3, 2] -> [1, 4, 2, 3, 5]。这是一个一般化过程。

从后往前看，如果有一个数破坏了递增，说明这个数移到后面去是可以提升字典序的（因为后面有比它大的数）。

那么把哪个数和它调换？因为要求下一个排列，肯定是比它大的最小的数。

换完以后容易发现现在递减的部分可以倒过来，进一步缩小字典序。

[3, 2, 1] -> [1, 2, 3]的情况竟然能被兼容，Python的负索引还真挺神奇。

1
class Solution:
2
    def nextPermutation(self, nums: List[int]) -> None:
3
        i = len(nums) - 1
4
        while nums[i] < nums[i - 1]:
5
            i -= 1
6
        i -= 1
7

8
        j = len(nums) - 1
9
        while nums[j] < nums[i]:
10
            j -= 1
11

12
        nums[i], nums[j] = nums[j], nums[i]
13

14
        nums[i+1:] = nums[i+1:][::-1]

98#

不用sort排序一个只含有0, 1, 2的数组。

这个问题叫荷兰国旗问题（名字加深印象）！

p0维护下一个0的位置，它的左边都是0。p2维护下一个2的位置，它的右边都是2。i是当前检查的位置。

循环的不变量：[0, p0)都是 0，(p2, n - 1]都是 2，中间[p0, i)都是 1。

把2交换到后面去的时候要再检查一次当前位置，因为被换到前面来的数可能是0或2。

在这个算法里，一个数做多会被搬两次。

1
class Solution:
2
    def sortColors(self, nums: List[int]) -> None:
3
        p0, i, p2 = 0, 0, len(nums) - 1
4
        while i <= p2:
5
            if nums[i] == 0:
6
                nums[i], nums[p0] = nums[p0], nums[i]
7
                p0 += 1
8
                i += 1
9
            elif nums[i] == 2:
10
                nums[i], nums[p2] = nums[p2], nums[i]
11
                p2 -= 1
12
            else:
13
                i += 1

97#

求一个数组里的绝对众数。

擂台法。同一个数字想成同一个门派，同门派就加一战斗力，不同门派就减一战斗力。绝对众数的门派肯定能站到最后。

1
class Solution:
2
    def majorityElement(self, nums: List[int]) -> int:
3
        ans, cnt = 0, 0
4
        for num in nums:
5
            if cnt == 0:
6
                ans = num
7
                cnt += 1
8
            else:
9
                cnt += 1 if x == ans else -1
10
        return ans