LeetCode热题100——技巧

1. 只出现一次的数字

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

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

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

提示：

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

1.3 解题代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < nums.length; ++i){
            res ^= nums[i];
        }
        return res;
    }
}

1.4 解题思路

1. 亦或运算解决问题。

2. 多数元素

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

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

提示：

• n == nums.length
• 1 <= n <= 5 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

2.3 解题代码

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

2.4 解题思路

1. 先对原来的数组进行排序。
2. 输出数组的中位数即为次数 大于 ⌊ n/2 ⌋ 的元素。

3. 颜色分类

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

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

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

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

提示：

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

3.3 解题代码

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        for(int i = 0; i <= right; ++i){
            while(i < right && nums[i] == 2){
                nums[i] = nums[right];
                nums[right] = 2;
                --right;
            }    
            if(nums[i] == 0){
                nums[i] = nums[left];
                nums[left] = 0;
                ++left;
            }
        }
    }
}

3.4 解题思路

1. 记录当前需要修改的数组左端为left，右端为right。
2. 如果当前为2，那么就一直将当前的数字与右端的数字交换，每交换一次，右端-1，直到右端为当前的数字的下标。
3. 如果当前为0，那么就将其与左端的数字交换，左端+1即可。
4. 直到遍历的下标到达右端时候为止。此时保证0都在最左段，2都在最右端，1都在中间。

4. 下一个排列

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

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

• 例如，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.length <= 100
• 0 <= nums[i] <= 100

4.3 解题代码

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        int j = n - 1;
        while(i >= 0){
            if(nums[i] < nums[i + 1]){
                while(j > i){
                    if(nums[j] > nums[i]){
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                    j--;
                }
                break;
            }
            i--;
        }
        int left = i + 1;
        int right = n - 1;
        while(left <= right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

4.4 解题思路

1. 对于 [1, 3, 2, 4]，只需要将2，4对换位置即可。
2. 对于 [4, 3, 2, 1]，需要将整个数组对换位置。
3. 对于 [1, 3, 4, 2]，下一个数是[1, 4, 2, 3]。需要将3和4对换位置，然后将[2, 3]换位置。
4. 所以设置双指针，数组长度为n，j为n - 1，i为 n - 2，只有当nums[i] < nums[i] + 1的情况下才有可能对当前后面的数进行操作。j开始自减，直到nums[i] < nums[j]，此时将nums[i]和nums[j]对换位置，将[i + 1, n - 1]反转。

5. 寻找重复数

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

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

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

5.3 解题代码

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

5.4 解题思路

1. 因为数组长度为n + 1，而数组中数字大小为[1, n]，所以可以将数组看做是一个有向图，下标 i 指向 数组下标nums[i]。
2. 因为存在相同的数，运用快慢指针，快指针每次在图中移动两次，慢指针移动一次，直到快慢指针接触，此时快指针已经在环中了。 下面所需要求的就是进环的那个节点。
3. 之后将慢指针回归原点，两个指针都以一格速度向前。假设环的长度为L，从起点到进入环的节点长度设为a，从环中走b步到达相遇位置，再走c步到达环口。则第一次相遇一定是在环内的。则2 * (a + b) = (a + b) + k * L， k >= 2且为整数。则 a = k * L - b，即 a = （k - 1）* L + C。此时指针走a步到达环口，快指针相当于绕了k - 1 圈后走了c步也到达了环口。这个时候即为最终的答案。