跳到主要内容

算法技巧练习

技巧类题目（Skills/Techniques）通常不属于单一的大类，涉及位运算、数学证明、排列逻辑或特定的统计方法。

136. 只出现一次的数字 (Single Number)​

题目描述​

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求不使用额外空间，且 O(n) 时间复杂度。

解题思路​

利用**异或（XOR）**运算的特性：

  1. x ^ x = 0
  2. x ^ 0 = x
  3. 异或满足交换律。 数组中出现两次的数异或后抵消，剩下的就是只出现一次的数。

Java 代码实现​

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
}

169. 多数元素 (Majority Element)​

题目描述​

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

解题思路​

摩尔投票法 (Boyer-Moore Voting Algorithm)。

  1. 选取第一个数为候选人 candidate，计票 count = 1。
  2. 遍历后续，若遇到相同数票数加一，不同数减一。若票数为 0，更换候选人。
  3. 最后的候选人就是多数元素。

Java 代码实现​

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0], count = 0;
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

75. 颜色分类 (Sort Colors)​

题目描述​

给定一个包含红色、白色和蓝色（0, 1, 2）的数组，原地对它们进行排序。

解题思路​

三路划分（荷兰国旗问题）。 维护三个指针。p0 指向 0 的边界，p2 指向 2 的边界，curr 遍历。

  • curr == 0：与 p0 交换，p0 和 curr 右移。
  • curr == 2：与 p2 交换，p2 左移，curr 不动。
  • curr == 1：curr 右移。

Java 代码实现​

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, curr = 0, p2 = nums.length - 1;
        while (curr <= p2) {
            if (nums[curr] == 0) {
                int tmp = nums[p0]; nums[p0++] = nums[curr]; nums[curr++] = tmp;
            } else if (nums[curr] == 2) {
                int tmp = nums[p2]; nums[p2--] = nums[curr];
            } else curr++;
        }
    }
}

31. 下一个排列 (Next Permutation)​

题目描述​

实现“下一个排列”函数，将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在，则升序排列。

解题思路​

  1. 从右往左寻找第一个降序的点 nums[i] < nums[i+1]。
  2. 在 i 右侧寻找第一个比 nums[i] 大的数 nums[j]。
  3. 交换两者。
  4. 反转并归序 i 右侧部分。

Java 代码实现​

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }
    private void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) swap(nums, start++, end--);
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
    }
}

287. 寻找重复数 (Find the Duplicate Number)​

题目描述​

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内。数组中至少存在一个重复的整数。要求不修改数组，且只能使用 O(1) 额外空间。

解题思路​

利用快慢指针（寻找环的入口）。 由于数字在 [1, n] 且长度为 n+1，可以将其视为一个链表：i -> nums[i]。

  1. slow = nums[slow], fast = nums[nums[fast]] 直到相遇。
  2. 重新设 ptr = 0，与 slow 指针同步前进再次相遇处即为重复点。

Java 代码实现​

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