217.重复的元素

一.题目描述

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示例 2：

输入：nums = [1,2,3,4]
输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

二.思路分析

思路一：（C语言）

使用两层循环，先使第一个元素与其他元素比较，相等则返回true,然后第二个元素与其他元素比较，依次执行；

此方法使用了两层循环，因此时间复杂度较高；

思路二：（C++）

先将数组中的元素从小到大排序，然后只需比较相邻两个元素是否相等即可；因为C++排序较为方便，所以此方法使用C++编写；若用C语言排序，可使用qsort（）函数；

思路三：（C++)

将数组中的元素装入哈希表中，可以直接按值查找，每次查找的时间复杂度为1；

三.解题代码

解法1：（C语言）

（自己第一次的写法，由于时间复杂度太高，AC不了）

#include
bool containsDuplicate(int* nums, int numsSize) {
	for (int i = 0; i < numsSize; i++)
	{
		for (int j = i + 1; j < numsSize; j++)
		{
			if (nums[i] == nums[j])
				return true;
		}
	}
	return false;
}

int main()
{
	bool ret;
	int nums[] = { 1,2,5,3,4,6,4 };
	int numsSize = sizeof(nums) / sizeof(nums[0]);
	ret = containsDuplicate(nums, numsSize);
	if (ret)
		printf("true\n");
	else
		printf("false\n");
	return 0;
}

解法二：

#include
using namespace std;
#include
#include

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
};

int main()
{

    vector<int> nums= { 2,3,4,5,6,2 };
    bool ret;
    Solution So;
	ret = So.containsDuplicate(nums);
	if (ret)
		printf("true\n");
	else
		printf("false\n");
	return 0;
}

解法三：

#include
using namespace std;
#include
#include

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (int x : nums) {
            if (s.find(x) != s.end()) {
                return true;
            }
            s.insert(x);
        }
        return false;
    }
};

int main()
{
    vector<int> nums{ 2,3,4,5,6,2 };
    bool ret;
    Solution So;
	ret = So.containsDuplicate(nums);
	if (ret)
		printf("true\n");
	else
		printf("false\n");
	return 0;
}

四.新知识点

1. vector容器初始化数组的方法：

   • vector nums={2,3,4,5,6};
   • vector nums{2,3,4,5,6};
   • vector nums(10,1); //初始化数组的内容为10个1

2. sort（）函数的使用

   sort()函数包含在#include头文件中；

   sort(start,end,排序方法)

   第一个函数为数组的起始地址，第二个参数为数组的终地址，第三个参数可不写，默认从小到大排序；

   //从小到大
   nums[5]={2,5,4,7,3};
   sort(nums,nums+5);
   
   //从大到小
   bool complare(int a,int b) //比较函数
   {return a>b;}
   sort(nums,nums+5,compare);
   
   //使用C++标准库
   sort(a,a+10,less<int>());	//从小到大
   sort(a,a+10,greater<int>());//从大到小
   
   //对字符排序，方法相同；
   char a[10]="asdfghjkl";
   sort(a,a+10,greater<char>());
   

3. C语言中排序函数qsort()使用

   int compare(const void*left,const void*right)
   {
       return *(int*)left-*(int*)right;	//从小到大排序
       //return *(int*)right-*(int*)left;	//从大到小排序
   }
   qsort(buf,num,size,compare);
   //buf:要排序数组的起始地址；
   //num:数组中元素个数；
   //size:数组中每个元素所占空间大小；
   //compare:比较规则，需要传递一个函数名；
   

   #include
   #include
   
   int compare(const void* left, const void* right)
   {
   	return *(int*)left - *(int*)right;
   }
   int main()
   {
   	int nums[] = { 21,83,32,96,27,4,55};
   	qsort(nums,7,sizeof(int),compare);
   	for (int i = 0; i < 7; i++)
   	{
   		printf("%3d", nums[i]);
   	}
   	return 0;
   }
   

4. unordered_set

   • unordered_set 容器提供了和 unordered_map 相似的能力，但 unordered_set 可以用保存的元素作为它们自己的键。T 类型的对象在容器中的位置由它们的哈希值决定，因而需要定义一个 Hash< T > 函数。基本类型可以省去Hash< T >方法。

   • 不能存放重复元素。

   • 可指定buckets个数，可进行初始化，也可后期插入元素

   • 无序集是一种容器，它以不特定的顺序存储惟一的元素，并允许根据元素的值快速检索单个元素。

   • 在unordered_set中，元素的值同时是唯一标识它的键。键是不可变的，只可增删，不可修改

   • 在内部，unordered_set中的元素没有按照任何特定的顺序排序，而是根据它们的散列值组织成桶，从而允许通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。

   • unordered_set容器比set容器更快地通过它们的键访问单个元素，尽管它们在元素子集的范围迭代中通常效率较低。

   • 容器中的迭代器至少是前向迭代器。

   初始化:

   unordered_set<int> set1; //创建空set
   unordered_set<int> set2(set1);    //拷贝构造
   unordered_set<int> set3(set1.begin(), set1.end());    //迭代器构造
   unordered_set<int> set4(arr,arr+5);    //数组构造
   unordered_set<int> set5(move(set2));    //移动构造
   unordered_set<int> set6 {1,2,10,10};//使用initializer_list初始化
   

   常用 *** 作:

   set1.find(2);    //查找2，找到返回迭代器，失败返回end()
   set1.count(2);    //返回指2出现的次数，0或1
   set1.emplace(3);    //使用转换移动构造函数，返回pair::iterator, bool>
   set1.insert(3);    //插入元素，返回pair::iterator, bool>
   set1.insert({1,2,3});    //使用initializer_list插入元素
   set1.insert(set1.end(), 4);//指定插入位置，如果位置正确会减少插入时间，返回指向插入元素的迭代器
   set1.insert(set2.begin(), set2.end());//使用范围迭代器插入
   set1.erase(1);	    //删除 *** 作，成功返回1，失败返回0
   set1.erase(set1.find(1));	    //删除 *** 作，成功返回下一个pair的迭代器
   set1.erase(set1.begin(), set1.end());    //删除set1的所有元素，返回指向end的迭代器
   set1.empty();        //是否为空
   set1.size();        //大小
   set1.bucket_count();    //返回容器中的桶数
   set1.bucket_size(1);    //返回1号桶中的元素数
   set1.bucket(1);    //1在哪一个桶
   set1.load_factor();    //负载因子，返回每个桶元素的平均数，即size/float(bucket_count);
   set1.max_load_factor();//返回最大负载因子
   set1.max_load_factor(2);//设置最大负载因子为2，rehash(0)表示强制rehash
   set1.rehash(20);//设置桶的数量为20，并且重新rehash
   set1.reserve(20);//将容器中的桶数设置为最适合元素个数，如果20大于当前的bucket_count乘max_load_factor，则增加容器的bucket_count并强制重新哈希。如果20小于该值，则该功能可能无效。
   unordered_set<int>::iterator it = set1.begin();	    //返回指向set1首元素的迭代器
   unordered_set<int>::const_iterator c_it = set1.cbegin();	    //返回指向set1首元素的常量迭代器
   unordered_set<int>::local_iterator it = set1.begin(1);//返回1号桶中的首元素迭代器
   unordered_set<int>::const_local_iterator c_it = set1.cbegin(1);//返回1号桶中的首元素的常量迭代器
   pair<unordered_set<int>::iterator, unordered_set<int>::iterator> it = set1.equal_range(1);//返回一个pair，pair里面第一个变量是lower_bound返回的迭代器，第二个迭代器是upper_bound返回的迭代器
   set1.clear();        //清空