数据结构基础day1

题目：136. 只出现一次的数字

要求时间线形复杂度，空间常数复杂度

解法：位运算异或

关于异或的性质：1. 与0异或等于本身；2. 与自己异或等于0；3. 异或运算有交换律和结合律

class Solution {
public:int singleNumber(vector<int>& nums) {int t=0;for(int num:nums) t = t^num;	//(a⊕a)⊕(a⊕a)⊕⋯⊕(a⊕a)⊕treturn t;}
};

题目：169. 多数元素

我的解法：（wrong）

没有初始化vector，且复杂度很高，注意使用vector和map的区别，map不用初始化大小。

class Solution {
public:int majorityElement(vector<int>& nums) {int n = nums.size(),ans;vector<int> counts;for(int num:nums){counts[num]++;}for(int i=0; i<counts.size(); ++i){if(counts[i]>n/2){ans = i;break;}}return ans;}
};

其他解法1：哈希表

class Solution {
public:int majorityElement(vector<int>& nums) {int ans, cnt=0;unordered_map<int, int> hash;	//使用hash表存储每个数字出现的次数，取出次数最多的数字for(int num:nums){++hash[num];if(hash[num]>cnt){	//在循环中直接记录最大值ans = num;cnt = hash[num];}}return ans;}
};

其他解法2：排序

排序后，众数会出现在n/2的位置

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());	//注意sort的写法，头和尾return nums[nums.size()/2];}
};

其他解法3：“占山头”

设置一个候选众数candidate和它出现的次数cnt（初始为0）
如果我们把众数记为+1，把其他数记为−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

class Solution {
public:int majorityElement(vector<int>& nums) {int candidate, cnt=0;for(int num:nums){if(cnt==0){	//如果目前没有候选者，当前元素成为候选者candidate=num;}if(candidate==num){	//是候选者，数量++++cnt;}else{	//不是候选者，数量--，直到等于0，设立新的候选者，众数数量最多，最后一定会是候选者--cnt;}}return candidate;}
};

题目：15. 三数之和

解法：排序➕双指针

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();if(n<3) return {};	//特判，元素个数小于3，返回空数组sort(nums.begin(), nums.end());	//排序vector<vector<int>> ans;	//存储答案for(int i=0; i<n; ++i){	//从头遍历if(nums[i]>0) return ans;	//如果目前元素为最小元素都大于0，则不可能存在这之后有三个元素加和等于0if(i>0 && nums[i]==nums[i-1]) continue;	//元素不能重复int k = -nums[i];	//求两数之和等于-nums[i]int t = n-1;		//尾指针int h = i+1;	//头指针while(h<t){	//外条件：头小于尾if(nums[h]+nums[t]>k){	//如果两数之和大于k，则尾指针前移--t;}else if(nums[h]+nums[t]==k){	//若等于k，则存储这三个数，同时移动头尾指针ans.push_back({nums[i], nums[h], nums[t]});--t; ++h;while(h<t && nums[h]==nums[h-1]) ++h;	//头指针不重复while(h<t && nums[t]==nums[t+1]) --t;	//尾指针不重复}else{	//若小于k，头指针后移++h;}}}return ans;	//返回答案}
};