【LeetCode 热题 100】只出现一次的数字 / 多数元素 / 颜色分类 / 寻找重复数

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto e : nums) res ^= e;
        return res;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> hashmap;
        int n = nums.size() / 2;
        int target = 0;
        for (auto e : nums)
        {
            if (++hashmap[e] > n)
            {
                target = e;
                break;
            }
        }
        return target;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int target = 0, cnt = 0;
        for (auto e : nums)
        {
            if (e == target) cnt++;
            else if (--cnt < 0)
            {
                target = e;
                cnt = 1;
            }
        }
        return target;
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = -1, r = nums.size(), i = 0;
        while (i < r)
        {
            if (nums[i] == 0) swap(nums[++l], nums[i++]);
            else if (nums[i] == 1) i++;
            else swap(nums[--r], nums[i]);
        }
    }
};

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

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = 0, slow = 0;
        do
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (fast != slow);
        slow = 0;
        while (fast != slow)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};