LeetCode Hot 100：技巧

LeetCode Hot 100：技巧

136. 只出现一次的数字

思路 1：哈希表

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hashMap;
        for (int& num : nums)
            hashMap[num]++;
        for (auto& [x, cnt] : hashMap)
            if (cnt == 1)
                return x;
        return -1;
    }
};

思路 2：异或

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

思路 3：排序

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; i += 2) {
            if (nums[i] != nums[i + 1])
                return nums[i];
        }
        return nums.back();
    }
};

169. 多数元素

思路 1：哈希表

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> hashMap;
        for (int& num : nums)
            hashMap[num]++;

        for (auto& [x, cnt] : hashMap)
            if (cnt > nums.size() / 2)
                return x;
        
        return -1;
    }
};

思路 2：排序

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

思路 3：摩尔投票算法（Boyer–Moore majority vote algorithm）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = nums[0];
        for (int &num : nums) {
            if (count == 0)
                candidate = num;
                
            if (candidate == num)
                count++;
            else
                count--;
        }

        return candidate;
    }
};

75. 颜色分类

思路 1：三指针

class Solution {
public:
    void sortColors(vector<int>& nums) {
        if (nums.size() < 2)
            return;

        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, nums.size() - 1] = 2
        int zero = 0, i = 0, two = nums.size();
        while (i < two) {
            if (nums[i] == 0) {
                swap(nums[zero], nums[i]);
                zero++;
                i++;
            } else if (nums[i] == 1)
                i++;
            else {
                two--;
                swap(nums[i], nums[two]);
            }
        }
    }
};

31. 下一个排列

思路 1：next_permutation

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};

思路 2：两遍扫描

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        // Step 1: 找到一个尽量靠右的「较小数」
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])
            i--;
        // Step 2: 找到一个在「较小数」右侧尽可能小的「较大数」
        if (i >= 0) {
            int j = n - 1;
            while (j > i && nums[j] <= nums[i])
                j--;
            // Step 3: 交换「较小数」和「较大数」
            swap(nums[i], nums[j]);
        }
        // Sterp 4: 「较大数」右边的数需要按照升序重新排列
        reverse(nums.begin() + i + 1, nums.end());
    }
};

思路 1：哈希表

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_map<int, int> hashMap;
        for (int& num : nums)
            hashMap[num]++;

        for (auto& [x, cnt] : hashMap)
            if (cnt >= 2)
                return x;

        return -1;
    }
};

287. 寻找重复数

思路 1：哈希表

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_map<int, int> hashMap;
        for (int& num : nums)
            hashMap[num]++;

        for (auto& [x, cnt] : hashMap)
            if (cnt >= 2)
                return x;

        return -1;
    }
};

思路 2：二分查找

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        int ans = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            for (int& num : nums)
                if (num <= mid)
                    count++;

            if (count <= mid)
                left = mid + 1;
            else {
                right = mid - 1;
                ans = mid;
            }
        }

        return ans;
    }
};

思路 3：二进制

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        // 确定二进制下最高位是多少
        int bit_max = 31;
        while (!((n - 1) >> bit_max))
            bit_max -= 1;

        int ans = 0;
        for (int bit = 0; bit <= bit_max; bit++) {
            int x = 0, y = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] & (1 << bit))
                    x += 1;
                if (i >= 1 && (i & (1 << bit)))
                    y += 1;
            }
            if (x > y)
                ans |= 1 << bit;
        }

        return ans;
    }
};

思路 4：快慢指针

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, 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;
    }
};