＜力扣刷题＞442. 数组中重复的数据

人生如逆旅，我亦是行人。————苏轼《临江仙·送钱穆父》

• 给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
• 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

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

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

输入：nums = [1]
输出：[]

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n
• nums 中的每个元素出现 一次 或 两次

• 由于给定的 n 个数都在 [1, n] 的范围内，如果有数字出现了两次，就意味着 [1,n] 中有数字没有出现过。
• nums 的所有整数都在范围 [1，n] 内，将题目给的数组当成一个哈希表，而哈希函数为：hash(value) = value − 1 ，
• 首先，我们的数组下标是 [0, n - 1] 的，而数据范围是 [1, n] ，如果数据范围内的数字每个都出现一次，那么很容易就能找到 nums[val - 1] = val 的哈希函数使得每个数值不重不漏的映射到唯一的数组下标，并填满整个数组。
• 若有整数出现不止一次，那么必定某些数值缺少，而缺失数值的位置被重复的数值占据了，我们只需调整数组满足上述的哈希映射，即可很容易找到重复的数据。

class Solution {
public:
    vector findDuplicates(vector& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = nums[i]; j != i + 1 && j != nums[j - 1]; j = nums[i]) {
                int tmp = nums[i];
                nums[i] = nums[j - 1];
                nums[j - 1] = tmp;
            }
        }
        vector ans;
        for (int i = 0; i < n; ++i)
            if (i != nums[i] - 1)
                ans.emplace_back(nums[i]);
        return ans;
    }
};

• 在许多应用程序中，都有交换相同类型的两个变量内容的需要。例如，在对整数数组进行排序时，将需要一个函数来交换两个变量的值，如下所示：

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

• 而在对一个数组字符串对象进行排序的时候，会需要以下函数：

void swap(string &a, string &b)
{
    string temp = a;
    a = b;
    b = temp;
}

• 因为这两个函数中代码的唯一区别就是被交换的变量的类型，所以这两个函数的逻辑与所有其他类似函数的逻辑都可以使用同一个模板函数来表示：

template
void swap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}

• 该函数在 头文件中声明。
• 下面的程序讲述如何使用这个库模板函数来交换两个变量的内容：

//这个程序演示了交换函数模板的使用。
#include 
#include 
#include  // Needed for swap
using namespace std;

int main ()
{
    // 获取并交换两个字符
    char firstChar, secondChar;
    cout << "Enter two characters: ";
    cin >> firstChar >> secondChar;
    swap(firstChar, secondChar);
    cout << firstChar << " " << secondChar << endl;
    // 获取并交换两个整型变量
    int firstInt, secondInt;
    cout << "Enter two integers: ";
    cin >> firstInt >> secondInt;
    swap(firstInt, secondInt);
    cout << firstInt << " " << secondInt << endl;
    //获取并交换两个字符串
    cout << "Enter two strings: ";
    string firstString, secondString;
    cin >> firstString >> secondString;
    swap(firstString, secondString);
    cout << firstString << " " << secondString << endl;
    return 0;
}

#include
#include 
using namespace std;

int main()
{
    //array用来保存一个3*3的二维数组，array的每个元素都是vector类型
    vector  >array;
    std::vector v;
    for (int i = 0; i <3; i++){
        for (int j = 0; j <3; j++){
            int value;
            cin >> value;
            v.push_back(value);
        }
        array.push_back(v); //保存array的每个元素
        v.clear();
    }

    for (int i = 0; i 

#include
#include 
using namespace std;

int main()
{
    vector  >array(3);//首先给array开辟了三个空间
    for (int i = 0; i <3; i++){
        array[i].resize(3);//给array中每个元素开辟了三个空间
        for (int j = 0; j <3; j++){
            cin >> array[i][j];//直接对开辟的空间赋值即可
        }
    }
    for (int i = 0; i