技巧

---

136. 只出现一次的数字

// 0开始一直遍历异或
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
}

169. 多数元素

// 还是先根据count进行判断是否更新候选者，然后判断候选者和当前num
class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int vote = 0;
        for (int num : nums) {
            if (vote == 0) {
                candidate = num;
            }
            vote += candidate == num ? 1 : -1;
        }

        return candidate;
    }
}

75. 颜色分类

参考来源

// i, j, k分别指向0, 1, 2下一个填充位置
// 0则i,j都右移
// 1则j右移继续遍历
// 2则j继续原地再次查看
class Solution {
    public void sortColors(int[] nums) {
        int i = 0, j = 0, k = nums.length - 1;
        while (j <= k) {
            if (nums[j] == 0) swap(nums, i++, j++);
            else if (nums[j] == 2) swap(nums, j, k--);
            else j++;
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

287. 寻找重复数

// 下标唯一，因此下标是每个节点地址
// 存放的值是val也是下一个元素地址，因此是地址重复
// 当slow和fast指针指向同一处时，说明两个节点的val也就是下一个地址相同
// 本题必定存在环，外面死循环即可
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;  // 地址都从0开始
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                slow = 0;
                while (slow != fast) {
                    slow = nums[slow];
                    fast = nums[fast];
                }
                return slow;
            }
        }
    }
}