[数据结构与算法]剑指offer-03找数组中任意重复数字c++

题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
一、基础知识
1、map和unordered_map（也就是通俗意义上的hash map）
这是C++的STL库实现的两种字典结构，都是通过键值对（key-value）存储数据的，键（key）和值（value）的数据类型可以不同。值（value）可以直接通过键（key）来访问，
a.hash_map基于hash table（哈希表）。内部元素无序。
优点： 因为内部实现了哈希表，因此其查找速度非常的快，查找的时间复杂度可达到O(1)（空间换时间）
缺点： 哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

b.map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。复杂度与树高相同，即O(logn)。
优点：
有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高
缺点： 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
适用处：对于那些有顺序要求的问题，用map会更高效一些

/*map中常用的操作
*begin()	还回指向map头部的迭代器
*clear()	删除所有元素，注意是所有元素
*count()	还回指定元素出现的次序
*empty()	如果map为空则还回true
*end()		还回指向map末尾的迭代器
*erase()	删除一个元素
*find()		查找一个元素
*insert()	插入一个元素
*max_size()	还回可以容纳的最大元素个数
*size()		还回map中元素的个数
*swap()		交换两个map
*/

int main() {
	map<int, char> m;
	//一、数据的插入
	m.insert(pair<int, char>(1, 'a'));
	m.insert(pair<int, char>(3, 'b'));
	m.insert(pair<int, char>(2, 'c'));
	m.insert(pair<int, char>(-1, 'd'));
	map<int, char>::iterator it = m.begin();
	for (; it != m.end(); it++) {
		cout << it->first << ":" << it->second << endl;
	}
	//二、数据的查找
	/*（1）使用find()函数，该函数可以找到key对应的value
	（2）使用count()函数,该函数的还回值只有0和1，1为找到，但是还回要查找的值*/
	it = m.find(1);
	if (it != m.end()) { cout << "find" << it->second << endl; }
	else { cout << "not find" << endl; }

	//三、map的清空
	//m.clear(m.begin(), m.end());

	//四、数据的删除
	//m.erase(it);

	//五、map的反向遍历，使用反向迭代容器
	
	for (map<int, char>::reverse_iterator Rit = m.rbegin(); Rit!=m.rend(); Rit++) {
		cout << Rit->first << ":" << Rit->second;
	}
	return 0;
}

2、vector用法
vector 是向量类型，它可以容纳许多类型的数据，如若干个整数，所以称其为容器。vector 是C++ STL的一个重要成员。

/*vector 的初始化*/
    (1) vector<int> a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初值，其值是不确定的。
   （2）vector<int> a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1
   （3）vector<int> a(b); //用b向量来创建a向量，整体复制性赋值
   （4）vector<int> a(b.begin(),b.begin+3); //定义了a值为b中第0个到第2个（共3个）元素
   （5）int b[7]={1,2,3,4,5,9,8};
        vector<int> a(b,b+7); //从数组中获得初值
  /*重要操作*/
  （1）a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
    （2）a.assign(4,2); //是a只含4个元素，且每个元素为2
    （3）a.back(); //返回a的最后一个元素
    （4）a.front(); //返回a的第一个元素
    （5）a[i]; //返回a的第i个元素，当且仅当a[i]存在2013-12-07
    （6）a.clear(); //清空a中的元素
    （7）a.empty(); //判断a是否为空，空则返回ture,不空则返回false
    （8）a.pop_back(); //删除a向量的最后一个元素
    （9）a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+         3（不包括它）
    （10）a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
    （11）a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
    （12）a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
    （13）a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8         ，插入元素后为1,4,5,9,2,3,4,5,9,8
    （14）a.size(); //返回a中元素的个数；
    （15）a.capacity(); //返回a在内存中总共可以容纳的元素个数
    （16）a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
    （17）a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
    （18）a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才         显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能） 
    （19）a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换
    （20）a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,<
 

二、c++参考答案

/*使用哈希表记录数组的各个数字，当查找到重复数字则直接返回。*/
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> map;//定义
        for(int num : nums) {
            if(map[num]) return num;
            map[num] = true;//map[num] 访问关键字为num的元素，如果num不在map中，添加一个关键字为num的元素，对其进行初始化。
        }//遍历数组 nums 中的每个数字 num：当num在dic中，说明重复，直接返回num

        return -1;
    }
};

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int i = 0;
        while(i < nums.size()) {
            if(nums[i] == i) {
                i++;
                continue;
            }//遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i] = i ）,
/*遍历中，第一次遇到数字 x 时，将其交换至索引 x 处；而当第二次遇到数字 x时，一定有 nums[x] = x，此时即可得到一组重复数字。*/
            if(nums[nums[i]] == nums[i])//代表索引 nums[i]处和索引 i 处的元素值都为nums[i] ，即找到一组重复值，返回此值 nums[i] ；
                return nums[i];
            swap(nums[i],nums[nums[i]]);//若 nums[i] = i ： 说明此数字已在对应索引位置，无需交换，因此跳过,否则： 交换索引为 i 和 nums[i]的元素值，将此数字交换至对应索引位置。
        }
        return -1;//若遍历完毕尚未返回，则返回 -1
    }
};