基础数字（一）位运算 哈希（数组中元素出现次数）
目录
力扣剑指 Offer II 070. 排序数组中只出现一次的数字
数组中只出现一次的数（其它数出现k次）_牛客题霸
数组中只出现一次的两个数字_牛客题霸_牛客网
数组中出现次数超过一半的数字_牛客题霸_牛客网
缺失的第一个正整数_牛客题霸_牛客网
力扣剑指 Offer II 070. 排序数组中只出现一次的数字
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
【解法一】前后一起比较
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
if(nums.size()==1) return nums[0];
if(nums[0]!=nums[1]) return nums[0];
for(int i=0;i<nums.size();){
if(nums[i]!=nums[i+1]) return nums[i];
i+=2;
}
return -1;
}
};【解法二】直接就是一个异或
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int res = 0;
for(auto e : nums)
res^=e;
return res;
}
};【解法三】二分法
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
while(left<right)
{
int mid = (left+right)>>1;
if(nums[mid] == nums[mid^1])
left = mid+1;
else
right = mid;
}
return nums[left];
}
};数组中只出现一次的数（其它数出现k次）_牛客题霸
给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。
已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。
请返回只出现了 1 次
数。
【解法一】排序之后进行逐k进行遍历
class Solution {
public:
int foundOnceNumber(vector<int>& arr, int k) {
// write code here
sort(arr.begin(), arr.end());
for(int i = 0; i < arr.size()-1; i += k)
{
if(arr[i] != arr[i+1])
return arr[i];
}
return arr[arr.size()-1];
}
};【解法二】使用哈希遍历一遍然后查找值为1的数
class Solution {
public:
int foundOnceNumber(vector<int>& arr, int k) {
// write code here
map<int,int>mp;
for(auto e : arr)
mp[e]++;
for(auto e : arr)
if(mp[e] == 1)
return e;
return -1;
}
};数组中只出现一次的两个数字_牛客题霸_牛客网
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围：数组长度 2≤n≤10002≤n≤1000，数组中每个数的大小 0<val≤10000000<val≤1000000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
【解法一】使用哈希遍历 注意运用mp接口的使用
class Solution {
public:
vector<int> FindNumsAppearOnce(vector<int>& array) {
// write code here
map<int, int>mp;
for(auto e : array)
{
mp[e]++;
}
vector<int> res;
for(auto it = mp.begin(); it!=mp.end(); it++)
{
if(it->second == 1)
res.push_back(it->first);
}
if(res[0]>res[1])
swap(res[0], res[1]);
return res;
}
};【解法二】使用异或运算
注意点 异或操作 0 XOR a = a a XOR a = 0
从第一个数开始俩俩之间进行异或操作，如果后一个数与前一个异或后的数不相等 只有俩种情况，一种是前面是俩相同的数，异或之后结果为0,0与第i个数不相同，这种只需要继续进行异或即可，还有一种是遇到了前后俩个数不相同情况，那么就是找到了，把当前i指向的数放入res数组中即可。找到一个后重新开始，将x重新初始为0，继续进行如此操作
class Solution {
public:
vector<int> FindNumsAppearOnce(vector<int>& array) {
// write code here
sort(array.begin(), array.end());
vector<int> res;
int x = 0;
for(int i = 0; i < array.size()-1; i++)
{
x ^= array[i];
if(array[i+1]!=x && x!=0)
{
res.push_back(array[i]);
x = 0;
}
}
if(res.size()==1)res.push_back(array.back());
return res;
}
};数组中出现次数超过一半的数字_牛客题霸_牛客网
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：n≤50000n≤50000，数组中元素的值 0≤val≤100000≤val≤10000
要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)
【解法一】排序取中
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
sort(numbers.begin(), numbers.end());
return numbers[numbers.size() / 2];
}
};【解法二】哈希表
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
map<int, int> mp;
int n = numbers.size();
for(auto e : numbers)
{
mp[e]++;
if(mp[e] > n/2)
return e;
}
return 0;
}
};缺失的第一个正整数_牛客题霸_牛客网
给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
进阶： 空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
数据范围:
−231≤nums[i]≤231−1−231≤nums[i]≤231−1
0≤len(nums)≤5∗1050≤len(nums)≤5∗105
【解法一】暴力查找（找之前排序一下哦 不然会超时 嘻嘻嘻）
class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
// write code here
sort(nums.begin(), nums.end());
int i = 1;
while(1)
{
if(find(nums.begin(),nums.end(),i++)==nums.end())
{
return i-1;
}
}
return 0;
}
};【解法二】哈希 跟我的方法一差不多诶，不过人家哈希表的find时间复杂度为O(1)慕了慕了
class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
// write code here
map<int, int>mp;
for(auto e : nums)
mp[e]++;
int res = 1;
while(mp.find(res) != mp.end())
res++;
return res;
}
};