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;
}
};