第一题:两数之和
解法1:(对于大规模数据,时间和空间复杂度会超出)
解题思路如下:
假设第一个数为a,用目标值c减去第一个数a,得到b,然后遍历后面的数,查看b是否在后面的数组中
class Solution {
public:
/**
*/
vector<int> twoSum(vector<int>& numbers, int target) {
int a,b;
vector<int> res;
for(int i=0;i<numbers.size();i++){
a=numbers[i];
b=target-a;
for(int j=i+1;j<numbers.size();j++){
if(b==numbers[j]){
res.push_back(i+1);
res.push_back(j+1);
return res;
}
}
}
return res;
}
};
解法2:(利用哈希表)
class Solution {
public:
/**
*
利用哈希表
*/
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
vector <int> res;
if (!n) //为空的话,直接返回
return res;
// 定义哈希表,unordered_map是用哈希表实现的,复杂度为O(1),而map是用红黑树实现的
unordered_map<int, int> hashmap; //第一个int表示值,第二个int表示下标
for (int i = 0; i < n; i ++) {
if ( hashmap.end() != hashmap.find(target - numbers[i]) ) { // find函数如果没有找到,会返回hashmap.end()
// 将结果存入数组
res.push_back(hashmap[target - numbers[i]] + 1);
res.push_back(i + 1);
break;
} else {
hashmap[numbers[i]] = i; // 将未找到的值插入哈希表中,继续遍历
}
}
return res;
}
};
第二题: 数组中出现次数超过一半的数字
解法1:(排序)
由于多数元素是指在数组中出现次数大于 【n/2】 的元素,那么将数组排序后,即便该元素是最小元素或是最大元素,其在数组中的覆盖范围也超过了数组中点(从左到右超过或是从右到左超过)。于是得到算法:
- 将数组排序;
- 返回数组中点元素nums[nums.size()/2] .
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
sort(numbers.begin(),numbers.end());
return numbers[numbers.size()/2];
}
};
是不是觉得很简单,多加两行代码就能搞定。(但是时间复杂度还是慢了)
时间复杂度: O(mlogm)。m为数组元素数,主要是排序的时间消耗。
空间复杂度: O(logm)。主要是系统sort函数需要的栈空间消耗。
解法2: (哈希)
如果考虑使用哈希表空间换时间,则可以降低时间复杂度。我们可以使用哈希表存储数组中元素出现的次数,当某个元素的出现次数超过一半时,返回该元素。于是得到算法:
- 1.初始化存储数组元素及其出现次数的哈希表map1,键为元素值,值为该元素在数组中的出现次数;
- 2.遍历数组元素,将被遍历数组元素的哈希值加一;
- 3.若该元素在数组中的出现次数超过数组元素数的一半,返回该元素。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
unordered_map<int, int> map1; //存储数组元素值及出现次数的哈希表
for(int i=0;i<numbers.size();i++){ //遍历数组元素
map1[numbers[i]]++;
if(map1[numbers[i]]>(numbers.size()/2)){ //若该元素出现此处超过一半
return numbers[i];
}
}
return 0;//为了能通过编译
}
};
解法3:(摩尔投票法)
该方法是网上看到的,觉得很有意思。
场景描述:
考虑这样一个场景,一群人打擂台,人群中分为不同的帮派,挨个上台比武。留在台上的帮派为擂主帮派,如果上台的人不是自己帮派的人,则将其干掉,代价是损失一个帮派成员;如果上台的人是自己帮派的人,则将其留下。则当所有人都参与完比武后,留在台上的必然是人数最多的帮派。
而在本题中,多数元素出现次数超过数组元素数的一半,也即,其他所有元素加起来都没多数元素多。如果我们记多数元素的值为1,其他元素的值为0,将数组中所有元素值相加,结果必然大于0。于是我们可以设计这样一种算法:
- 1.初始化候选答案ans为nums[0],初始化数值计算结果count为0;
- 2.遍历数组若该元素与备选答案相等,count加一,否则减一;
- 3.若count减为零,更换备选答案ans为当前元素,重置count为1,继续遍历后续元素。遍历完成后返回最终的ans即为多数元素。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int ans = nums[0];//初始化候选答案为nums[0]
int count = 0;//初始化数值计算结果为0
for(auto num : nums){//遍历数组
if(num==ans) ++count;//若该元素与备选答案相同,则count加一
else{//否则减一
--count;
if(count==0){//若count减为0
ans = num;//更换备选答案为当前元素
++count;//重置count为1
}
}
}
return ans;//返回答案
}
};
第三题: 数组中只出现一次的两个数字
这道题其实和第二题很类似,因此有差不多的解法,解题思路如下:
- 定义一个哈希表<int,int>,第一个数表示值,第二个数表示出现的次数,利用for循环遍历array,然后找出第二个int为1的两个数
- 直接返回这两个数
class Solution {
public:
/**
思路:
step1:定义一个哈希表<int,int>,第一个数表示值,第二个数表示出现的次数,利用for循环遍历array,然后找出第二个int为1的两个数
step2:直接返回这两个数
*/
vector<int> FindNumsAppearOnce(vector<int>& array) {
unordered_map<int, int> map1; //存储数组元素值及出现次数的哈希表
vector<int> a;
for(int i=0;i<array.size();i++){
map1[array[i]]++;
}
for(int i=0;i<array.size();i++){
if(map1[array[i]]<2){
a.push_back(array[i]);
}
}
sort(a.begin(),a.end()); //题目要求输出的结果按照非降序排列
return a;
}
};
第四题:缺失的第一个正整数
数组nums的长度为n,所以正整数的范围为【1,n+1】,因此缺失的第一个正整数要么在 [1,n] 中,要么是n+1。
解法1: 哈希
- 首先遍历整个数组,并用unordered_map标记该数字已出现
- 然后从1遍历到n,并在unordered_map查找该值是否出现,未出现则直接返回
- 若长度为n的数组里n个数字都出现了,则第n+1个数字一个未出现
class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
int n=nums.size();
unordered_map<int,int>m;
for(int i=0;i<n;i++){//统计每个数字出现的次数
m[nums[i]]++;
}
for(int i=1;i<=n;i++){//出现次数为0的直接返回
if(m[i]==0)return i;
}
return n+1; //运行到这一步,说明确实的数为n+1
}
};
时间复杂度和空间复杂度分析:
- 时间复杂度:O(n),遍历了一次长度为n的数组和枚举一次长度n-1的数
- 空间复杂度:O(n),建立了长度为n的哈希表
解法2: 排序后直接遍历
- 对输入的数组进行排序
- 遍历一次数组,不是正整数的数则统计其个数,是正整数则按序从1开始往后逐次比较,比较不成功的则直接返回
- 最后若能遍历完数组,说明这是一串从1开始连续的数组,则返回n+1即可
class Solution {
public:
int minNumberDisappeared(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size(),cn=0,cn2=0;
for(int i=0;i<n;i++){
if(nums[i]<=0)cn++;//不是正整数的数则统计其个数
else if(nums[i]!=++cn2)return cn2;//是正整数则按序从1开始往后逐次比较,比较不成功的则直接返回
}
return n-cn+1;
}
};
eg1: 排序后的数组为[-2,-1,0,1,3,4],这个例子会执行到i=4即3这个位置就停下,因为3!=2,return cn2=2;
eg2: 排序后的数组为[1,2,3,4,5],for循环会执行完毕,且cn==0,return 5-0+1即return 6.
第五题:三数之和
解法1: 暴力搜索
时间复杂度: O(nlogn) +O(n^3);排序算法O(nlogn)+三重循环枚举
空间复杂度: O(n);数组存储与读取数据
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int>>ans;
if(num.size()<3)return ans;
sort(num.begin(),num.end());//排序使最后结果满足非降序排列
for(int i=0;i<num.size()-2;i++){
//注意细节:如果循环的当前数和之前一样,则continue
//即如果数组中出现了先前已经找过的重复数字,则不必再找了
if(i&&num[i]==num[i-1])continue; //其实这里还不算完整,因为可能会出现隔几个数相同的情况。
for(int j=i+1;j<num.size();j++){ //不重复选择当前数加1
if(j>i+1&&num[j]==num[j-1])continue;
for(int k=j+1;k<num.size();k++){
if(k>j+1&&num[k]==num[k-1])continue;
if(num[i]+num[j]+num[k]==0){
ans.push_back({num[i],num[j],num[k]});//最后输入按非降序排列
}
}
}
}
return ans;
}
};
解法2: 双指针优化(该方法来自牛客网精华题解,非常值得学习)
具体思路:
- 首先对输入的数据的大小进行判断,如果数小于3个,那么直接返回空。
- 对输入的数据进行排序,注意排完序后第一个数肯定是负数,除非是0、0、0这种情况的
- for循环选择第一个数x,然后创建两个指针i和j,指针i指向x的下一个数,指针j指向最后一个数。
- 因为x肯定小于0,所以若指针i 加指针j 大于当前数x的相反数,则指针j --;若指针i 加指针j 小于当前数x的相反数,则指针i++;若指针i 加指针j 等于当前数x的相反数,则答案为x 和指针i 与j 的三元组。
- 若x>0,那么return 空;
时间复杂度: O(nlogn) + O(n^2);排序算法O(nlogn)+双指针
空间复杂度: O(n);数组存储与读取数据
下图演示了双指针算法过程:
具体代码如下:
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int>>ans;
if(num.size()<3)return ans;
sort(num.begin(),num.end());
for(int i=0;i<num.size()-2;i++){
if(num[i]==num[i-1]&&i)continue;
int l=i+1,r=num.size()-1;
while(l<r){
if(num[l]+num[r]==-num[i]){//若指针i 加指针j 等于当前数x 则答案为x 和指针i 与j 的三元组。
ans.push_back({num[i],num[l],num[r]}); //可以同时插入三个数
while(num[l]==num[l+1]&&l+1<r)l++; //如果后面的数和前面的一样,那么忽略掉
while(num[r]==num[r-1]&&r-1>l)r--;
l++,r--; //指针继续移动,查看后面还有没有组合
}
else if(num[l]+num[r]>-num[i]){//若指针l 加指针r 大于当前数-num[i]则指针r --,
r--;
}
else l++;//若指针l 加指针r 小于当前数-num[i]则指针l++,
}
}
return ans;
}
};
注: 以上题目都是在牛客网的剑指offer题库中刷的,有自己做的,也有不会做看别人精华解题思路,然后总结的。如果侵犯了您的权益,请私聊我。
最后,觉得本文内容对你有所帮助的话,感谢点赞收藏,在我的剑指offer专栏还有相关的算法刷题文章,等待您的阅读!文章来源:https://www.toymoban.com/news/detail-417352.html
导航链接:必刷算法题—二分查找(C++)
导航链接:必刷算法题—排序篇(C++)
导航链接:剑指—树篇(C++)
导航链接:剑指—动态规划篇(C++)
导航链接:剑指—链表篇(C++)
导航链接:剑指—队列&栈篇(C++)文章来源地址https://www.toymoban.com/news/detail-417352.html
到了这里,关于必刷算法题之哈希篇(题目及代码)---C++的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!