目录

技巧类题目

136 只出现一次的数字

191 位1的个数

231. 2 的幂

169 多数元素

75 颜色分类 （双指针）

287. 寻找重复数

136 只出现一次的数字

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

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

---

这里就可以运用异或运算的性质：

一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。

对于这道题目，我们只要把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素。

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int n : nums) {
            res ^= n; //落单的数字和 0 做异或还是它本身
        }
        return res;
    }
}

191 位1的个数

n & (n-1) 这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1

不断消除数字 n 中的 1，直到 n 变为 0。

public class Solution {
    // 你需要将 n 视为一个无符号值
    public int hammingWeight(int n) {
        int res = 0; // 结果变量，用于存储1的个数      
        // 当 n 不为0时，继续循环
        while (n != 0) {
            // n & (n - 1) 每次操作都会将 n 的最右边的一个1置为0
            // 这一步可以消除最右边的一个1
            n = n & (n - 1);     
            // 每次消除一个1，计数器加1
            res++;
        }
        // 返回1的个数
        return res;
    }
}

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2(x) ，则认为 n 是 2 的幂次方。

---

一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1。

位运算 n&(n-1) 在算法中挺常见的，作用是消除数字 n 的二进制表示中的最后一个 1，用这个技巧可以判断 2 的指数。

• 2^0 = 1，二进制表示为 0001。
• 2^1 = 2，二进制表示为 0010。
• 2^2 = 4，二进制表示为 0100。
• 2^3 = 8，二进制表示为 1000。

class Solution {
    public boolean isPowerOfTwo(int n) {
        // 如果 n 小于等于 0，则 n 不是 2 的幂
        if (n <= 0) return false;
        
        // 位操作判断 n 是否是 2 的幂
        // 对于 2 的幂，二进制表示中只有一个 1，其余全是 0
        // 比如：2 (10), 4 (100), 8 (1000), 等等
        // n & (n - 1) 将会移除 n 最右边的 1，如果 n 是 2 的幂，结果将是 0
        // 例如：n = 8, 二进制表示为 1000
        // n - 1 = 7, 二进制表示为 0111
        // n & (n - 1) = 1000 & 0111 = 0000
        return (n & (n - 1)) == 0;
    }
}

169 多数元素

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

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

---

计数逻辑：

• 计数器为0：如果 count 为0，说明当前没有候选元素，或者之前的候选元素已经被其他元素抵消掉了。因此，更新 target 为当前元素，并将 count 设为1。
• 当前元素等于目标元素：如果当前元素 nums[i] 等于 target，说明当前元素依旧是多数元素的候选，计数器加1。
• 当前元素不等于目标元素：如果当前元素 nums[i] 不等于 target，说明遇到了一个不同的元素，计数器减1。

class Solution {
    public int majorityElement(int[] nums) {
        // 定义目标元素和计数器
        int target = 0;
        int count = 0;
        
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 如果计数器为0，表示需要选择一个新的目标元素
            if (count == 0) {
                // 将当前元素设为目标元素
                target = nums[i];
                // 计数器重置为1
                count = 1;
            } else if (nums[i] == target) {
                // 如果当前元素等于目标元素，计数器加1
                count++;
            } else {
                // 如果当前元素不等于目标元素，计数器减1
                count--;
            }
        }
        
        // 返回最后确定的目标元素
        return target;
    }
}

75 颜色分类 （双指针）

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

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

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

---

class Solution {
    public void sortColors(int[] nums) {
        int n0 = 0, n1 = 0;
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i]; // 获取当前元素
            nums[i] = 2; // 默认将当前元素置为 2

            // 如果当前元素小于 2，则需要处理 1 的插入
            if (num < 2) {
                nums[n1++] = 1; // 将 1 插入到 n1 的位置，并将 n1 向前移动一位
            }

            // 如果当前元素小于 1，则需要处理 0 的插入 如果是0 前面设置过一次会被覆盖
            if (num < 1) {
                nums[n0++] = 0; // 将 0 插入到 n0 的位置，并将 n0 向前移动一位
            }
        }
    }
}

287. 寻找重复数

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

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

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

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 和 fast 相遇，表明存在一个循环（环）

        // 第二阶段：找到环的入口，即重复的元素
        int a = 0; // a 从头开始
        int b = fast; // b 从相遇点开始
        while (a != b) {
            a = nums[a]; // a 和 b 同时以相同速度前进
            b = nums[b];
        }
        // 当 a 和 b 再次相遇时，相遇点即为环的入口，也就是重复的数字
        return a;
    }
}