hot100 技巧

打算在这系列博客把hot100的题扫一遍，分模块来。

只出现一次的数字题目描述：

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

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

输出：1

示例 2 ：

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

输出：4

示例 3 ：

输入：nums = [1]

输出：1

提示：

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次。

思路：

参照136. 只出现一次的数字 - 力扣（LeetCode）

代码：

  
var singleNumber = function(nums) {
    let ans = 0;
    for (const x of nums) {
        ans ^= x;
    }
    return ans;
};

多数元素题目描述：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

提示：

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
输入保证数组中一定有一个多数元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路：

map思路很好想，还有一种做法叫摩尔投票，不同元素互相抵消，因为多数元素超过一半，抵消完剩余的就是多数元素。

灵神的通俗解释169. 多数元素 - 力扣（LeetCode）

代码：

map：

  
var majorityElement = function(nums) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i])) {
            map.set(nums[i], map.get(nums[i]) + 1);
        } else {
            map.set(nums[i], 1);
        }
        if (map.get(nums[i]) > nums.length / 2) {
            return nums[i];
        }
    }
    
};

摩尔投票：

  
var majorityElement = function(nums) {
    let candidate = 0, count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (count === 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] === candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
};

颜色分类题目描述：

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

思路：

很显然是一个排序问题，题目里要求原地排序，所以可以考虑选择排序、冒泡排序和插入排序等，但这些方法要么需要逐个比较，要么需要逐个修改，时间复杂度是很高的。考虑到本题的数组只有三种重复元素，可以考虑使用直接计数排序，可以在第一次遍历时收集三个元素的信息，在第二遍时进行修改。这样时间复杂度是o(n)，空间复杂度是o(1)。

如果想进一步优化到一趟扫描，可以参考灵神的思路75. 颜色分类 - 力扣（LeetCode）

代码：

先收集，后分配：

  
var sortColors = function(nums) {
    // 第一遍：数
    let cnt0 = 0, cnt1 = 0, cnt2 = 0;
    for (let x of nums) {
        if (x === 0) cnt0++;
        else if (x === 1) cnt1++;
        else cnt2++;
    }
    // 第二遍：填
    let idx = 0;
    while (cnt0-- > 0) nums[idx++] = 0;
    while (cnt1-- > 0) nums[idx++] = 1;
    while (cnt2-- > 0) nums[idx++] = 2;
};

一趟扫描，采用类似插入排序的思想，每往后遍历一步，都维护前面的有序子序列，为了保证子序列可能没有2而会导致的冲突，从2开始从前往后修改：

  
var sortColors = function(nums) {
    let p0 = 0, p1 = 0;
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        nums[i] = 2;
        if (x <= 1) {
            nums[p1++] = 1;
        }
        if (x === 0) {
            nums[p0++] = 0;
        }
    }
};

下一个排列题目描述：

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

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

思路：

字典序即从前到后逐位比较。

[1,2,3] < [1,3,2] 第2位 2<3，所以前面小
[1,2,3] < [2,1,3] 第1位 1<2，后面不用看了
[1,1,5] < [1,5,1] 第2位 1<5

因此，为找到的下一个排列保证是下一个字典序更大的排列，这两个数组的左侧应该是尽量相似的。因此本题的考虑会是尽量修改数组的右侧，而不修改左侧。

以[1, 3, 5, 4, 2]为例，可以分三步走：

第1步：从右往左，找第一个”上升”的位置。这一步尽量让数组的左侧相同，最小程度地修改右侧。

第2步：在3右边，找比3大的最小值。这一步保证最小程度的增大，也代表着下一个字典序的构建。

第3步：把i+1到末尾反转。交换后，i右边一定还是递减的（因为原来递减，只换了一个更大的进来，不影响顺序）。反转它变成递增，就是最小的后缀。这就是原排列的下一个字典序排列。前缀已经变大，后缀即取最小。

具体可以参考灵神的讲解，将下一个排列和下一个整数类比得非常清晰31. 下一个排列 - 力扣（LeetCode）

下一个排列	下一个整数	相同点
从右到左，找第一个小于右侧相邻数的数 x	从右到左，找第一个小于 9 的数字 x	都是找第一个小于右侧相邻数的数
找 x 右边最小的大于 x 的数 y，交换 x 和 y	把 x 加一，得到 y=x+1	增大这个数
反转 y 右边的数，把右边的数变成最小的排列	把 y 右边的数字都变成 0	把右边的数变到最小

代码：

  
var nextPermutation = function(nums) {
    const n = nums.length;

    // 第1步：从右找第一个 nums[i] < nums[i+1]
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;

    if (i >= 0) {
        // 第2步：从右找第一个比nums[i]大的
        let j = n - 1;
        while (nums[j] <= nums[i]) j--;
        [nums[i], nums[j]] = [nums[j], nums[i]]; // 交换
    }

    // 第3步：反转i+1到末尾（i=-1时反转整个数组）
    let left = i + 1, right = n - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++; right--;
    }
};

寻找重复数题目描述：

给定一个包含 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 = [3,3,3,3,3]
输出：3

思路：

一般处理这种题目的思维可能是哈希表，排序等，但这题最难的地方在于要将这个数组理解成链表，某个数组元素存的值，即为这个数组元素指向的下一个数组元素，即i = nums[i]等价于node = node.next。

理解这一点之后，就不难以发现，这个链表对应的有向图是一个有环图，入度不止为1的节点就是重复元素，这个元素会是入环口。这种图被称为基环树。

剩余的思路类似于142. 环形链表 II - 力扣（LeetCode），可以使用快慢指针解决。

另外在写代码时需要注意，本题已经保证有环，而环形链表2是不确定有环的，因此在写循环判断条件时有所不同。如果slow和fast都从零开始，就要考虑用dowhile了，因为第一次比较时，slow和fast肯定是相同的。

287. 寻找重复数 - 力扣（LeetCode）

代码：

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

    // 阶段1：快慢指针找相遇点，因为一开始相等，不能用while，需要先执行一次
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);

    // 阶段2：从起点和相遇点同速走，找入环口
    let headPoint = 0;
    let startPoint = slow;

    while (headPoint !== startPoint) {
        headPoint = nums[headPoint];
        startPoint = nums[startPoint];
    }
    return headPoint;
};

hot100 技巧

只出现一次的数字 题目描述：

思路：

代码：

多数元素 题目描述：

思路：

代码：

颜色分类 题目描述：

思路：

代码：

下一个排列 题目描述：

思路：

代码：

寻找重复数 题目描述：

思路：

代码：

相关文章

hot100 图论

hot100 二分查找

hot100 栈

只出现一次的数字题目描述：

多数元素题目描述：

颜色分类题目描述：

下一个排列题目描述：

寻找重复数题目描述：