136. 只出现一次的数字❌
如果能用sort函数或者set容器就很简单,可惜不允许
异或解决
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int num : nums) {
res ^= num;
}
return res;
}
};
169. 多数元素✅
以空间换脑细胞 直接map+set
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> mp;
unordered_set<int> st;
for(int &num : nums) {
st.insert(num);
mp[num]++;
}
for(auto &num : st) {
if(mp[num] > nums.size() / 2) return num;
}
return 0;
}
};
75. 颜色分类✅
统计一下各颜色数量,再原地修改数组
class Solution {
public:
void sortColors(vector<int>& nums) {
int cnt[3] = {0, 0, 0};
for(int num : nums) cnt[num]++;
for(int i = 0; i < cnt[0]; i++) nums[i] = 0;
for(int i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;
for(int i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;
}
};
31. 下一个排列❌
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int pos1 = -1, pos2;
for(int i = nums.size() - 1; i > 0; i--) {
if(nums[i] > nums[i-1]) {
pos1 = i;
break;
}
}
if(pos1 == -1) { //说明是最大排列
reverse(nums.begin(), nums.end());
return ;
}
for(int i = nums.size() - 1; i >= 0; i--) {
if(nums[i] > nums[pos1 - 1]) {
pos2 = i;
break;
}
}
cout << "pos1:" << pos1 << " " << "pos2:" << pos2 << endl;
swap(nums[pos1-1], nums[pos2]);
reverse(nums.begin() + pos1, nums.end());
}
};
287. 寻找重复数❌
不能修改数组且只能用常量级额外空间
「二分查找」的思路是先猜一个数(搜索范围[left..right]里位于中间的数mid),然后统计原始数组中小于等于mid的元素的个数count:如果count严格大于mid,根据抽屉原理,重复元素就在区间[left..mid]里;否则,重复元素可以在区间[mid + 1..right]里找到
不是二分数字,而是二分下标,因为下标是有序的
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() - 1, mid, count;
while(left < right) {
mid = (left + right) / 2;
count = 0;
for(int &num : nums) {
if(num <= mid) count++;
}
if(count > mid) right = mid;
else left = mid + 1;
}
return left;
}
};