【C++】vector OJ练习——只出现一次的数字|| &&删除有序数组中的重复项&&数组中出现次数超过一半的数字
【摘要】 4. 只出现一次的数字 II题目链接: link思路讲解这道题还是让我们找出数组中只出现一次的那个数字，但是与第一题不同的是，其余数字均出现三次。那我们用第一题的方法肯定是不行了，那我们可以怎么做呢？我们后面学了unordered_map的话用unordered_map其实可以很容易解这道题，不过我们现在还没学。那这里我就用了一种比较暴力的方法，也很好理解：怎么做呢？遍历数组，一次取每个元素...
4. 只出现一次的数字 II
题目链接: link
思路讲解
这道题还是让我们找出数组中只出现一次的那个数字，但是与第一题不同的是，其余数字均出现三次。
那我们用第一题的方法肯定是不行了，那我们可以怎么做呢？
我们后面学了unordered_map的话用unordered_map其实可以很容易解这道题，不过我们现在还没学。
那这里我就用了一种比较暴力的方法，也很好理解：
怎么做呢？
遍历数组，一次取每个元素与其余元素进行比较，如果出现相等的情况，那就说明当前元素不是我们要找的数字，那就看下一个，如果某个元素与其余数字都不想等，就是要找的目标数字。
当然效率可能没有那么高。
AC代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(int i=0;i<nums.size();++i)
{
int flag=1;
for(int j=0;j<nums.size();++j)
{
if(i==j)
continue;
if(nums[i]==nums[j])
{
flag=0;
break;
}
}
if(flag)
{
ret=nums[i];
break;
}
}
return ret;
}
};
5. 删除有序数组中的重复项
题目链接: link
思路讲解
这道题我们可以考虑使用“双指针”来求解：
首先，定义两个变量作为指针，初始都指向下标为0位置。
如果两指针指向的元素相等，我们只让 src++往后走，过滤掉重复值。
如果不再相等，先让dest++，让后把src指向的元素赋值给dest指向的元素，然后再让src++。
然后再判断两指针指向的元素是否相等，重复上述操作，直至src遍历完数组。
最终dest+1就是去重后的数组长度。
AC代码
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int dest=0;
int src=0;
while(src<nums.size())
{
if(nums[src]==nums[dest])
++src;
else
{
// ++dest;
// nums[dest]=nums[src];
// ++src;
nums[++dest]=nums[src++];
}
}
return dest+1;
}
};
6. 数组中出现次数超过一半的数字
题目链接: link
思路讲解
这道题其实有一个很简单的解法：
怎么做呢？
只要给这个数组排下序就行了，然后直接返回排好序之后数组中间的那个元素即可。
因为我们要找的数字在数组中出现的次数超过数组长度的一半，所以排好序之后中间位置的元素肯定是这个出现的次数超过数组长度的一半的元素。
AC代码
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
sort(numbers.begin(),numbers.end());
return numbers[numbers.size()/2];
}
};
这篇文章的内容就到这里，欢迎大家指正！！！
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）