给你一个整数数组nums,如果任一值在数组中出现至少两次,返回true;如果数组中元素互不相同,返回false。
2. 解法 2.1 排序示例
输入:nums=[1,2,3,1]
输出:true
利用sort函数将数组排序,那么重复元素一定相邻,基于此编写程序。
class Solution {
public:
bool containsDuplicate(vector<int>& nums)
{
if(nums.size() < 2) return false;
sort(nums.begin(),nums.end());
for(int i = 0; i!=nums.size()-1;)
{
if(nums.at(i+1) == nums.at(i))
{
return true;
}
else
{
++i;
}
}
return false;
}
};
2.2 哈希
容器set中只会保留不重复的元素,将nums中元素插入set中,如果每个数都插入成功,则不包含重复元素,返回false,否则返回true。
set.insert()函数的返回值为pair(iterator,bool),第一个参数表示插入数据的迭代器,第二个表示是否插入成功,因此可以用第二个参数表示插入成功与否。
class Solution {
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int> s;
for(auto r : nums)
{
auto res = s.insert(r).second;
if(!res)//如果插入不成功,表明有重复元素
{
return true;
}
}//循环走完,未发现重复元素
return false;
}
};
只出现一次的数字
这一题遇上一题有相似的解法,因此放到一起。
1. 只出现一次的数字给定一个非空整数数组,除了某个元素只出现一次外,其余每个元素均出现两次。找出那个只出现一次的元素。
说明:
你的算法应该具有线性时间复杂度。或者
O
(
1
)
O(1)
O(1)的空间复杂度。
2. 解法 2.1 哈希示例
输入:[2,2,1]
输出:1
看到重复数字,想到哈希。上一题是利用哈希表能否插入判断是否有重复元素,这一题同样利用这一点,但是思路得多一层,不仅得知道插入是否成功,还得把第二次不成功但是第一次成功的元素删除。
class Solution {
public:
int singleNumber(vector<int>& nums)
{
unordered_set<int> s;
for(int r : nums)
{
if(!s.insert(r).second)//如果r插入不成功
{
s.erase(r);//那么删除之前插入的r
}
}
return *s.begin();//最后只会剩下一个元素,就是我们需要的只出现一次的元素
}
};
2.2 位运算
异或运算规则为:相同为0,相异为1。对于int类型的数据a,b,c,有如下的运算规则:
0^a = a
a^a = 0
a^ b ^ c = a ^ c ^ b
用vs测试,cout << a^b输出结果为 a+b的值
根据以上规则,倘若我们把nums中的所有元素异或,那么相同的值异或为0,最后只剩下只出现一次的元素。
class Solution {
public:
int singleNumber(vector<int>& nums)
{
int ans = 0;
for(int i = 0; i != nums.size(); ++i)
{
ans ^= nums.at(i);
}
return ans;
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)