力扣hot100——技巧
136. 只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (auto x: nums) ans ^= x;
return ans;
}
};
位运算,异或消去重复的元素
169. 多数元素
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
map<int, int> mp;
for (int i = 0; i < n; i++) {
mp[nums[i]]++;
if (mp[nums[i]] > n / 2) return nums[i];
}
return 0;
}
};
桶计数
75. 颜色分类
class Solution {
public:
void sortColors(vector<int>& a) {
int k = 0;
for (int i = 0; i < a.size(); i++) {
if (!a[i]) {
swap(a[i], a[k++]);
}
}
for (int i = k; i < a.size(); i++) {
if (a[i] == 1) {
swap(a[i], a[k++]);
}
}
}
};
我们可以考虑对数组进行两次遍历。在第一次遍历中,我们将数组中所有的 0 交换到数组的头部。在第二次遍历中,我们将数组中所有的 1 交换到头部的 0 之后。此时,所有的 2 都出现在数组的尾部,这样我们就完成了排序。
31. 下一个排列
class Solution {
public:
void nextPermutation(vector<int>& a) {
for (int i = a.size() - 1; i >= 1; i--) {
if (a[i] > a[i - 1]) {
for (int j = a.size() - 1; j >= i; j--) {
if (a[j] > a[i - 1]) {
swap(a[i - 1], a[j]);
break;
}
}
reverse(a.begin() + i, a.end());
return ;
}
}
reverse(a.begin(), a.end());
}
};
思维题:
序列后缀是单调不增的,因此从后往前找到第一个拐点(i - 1),然后将这个元素与后缀中从后往前大于它的第一个元素交互,之后后缀再从小到大排序(翻转)即可
287. 寻找重复数
class Solution {
public:
int findDuplicate(vector<int>& a) {
int n = a.size();
int l = 0, r = n;
auto check = [&](int x) -> bool {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] <= x) cnt++;
}
return cnt <= x;
};
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l + 1;
}
};
我的推理:
假设答案是ans,小于ans的数最多有ans - 1个,大于ans的数最多有n - ans个,设ans的个数有x个
因此总个数 n + 1 <= ans - 1 + n - ans + x
得 x >= 2
官方题解:
考虑 nums 数组一共有 n+1 个位置,我们填入的数字都在 [1,n] 间,有且只有一个数重复放了两次以上。对于所有测试用例,考虑以下两种情况:
- 如果测试用例的数组中 target 出现了两次,其余的数各出现了一次,这个时候肯定满足上文提及的性质,因为小于 target 的数 i 满足 cnt[i]=i,大于等于 target 的数 j 满足 cnt[j]=j+1。
- 如果测试用例的数组中 target 出现了三次及以上,那么必然有一些数不在 nums 数组中了,这个时候相当于我们用 target 去替换了这些数,我们考虑替换的时候对 cnt[] 数组的影响。如果替换的数 i 小于 target ,那么 [i,target−1] 的 cnt 值均减一,其他不变,满足条件。如果替换的数 j 大于等于 target,那么 [target,j−1] 的 cnt 值均加一,其他不变,亦满足条件。