11 错误的集合

作者: Turbo时间限制: 1S章节: 课程设计

问题描述 :

集合 s 包含从 1 到 n 的整数，并且按升序排列。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数。

示例 1：

输入：

4

1 2 2 4

输出：

2 3

示例 2：

输入：

2

1 1

输出：

1 2

输入说明 :

输入两行：

第一行为一个整数n代表数组nums的长度。

第二行输入n个整数代表数组nums的元素。

提示：

    2 <= n <= 10^4

    1 <= nums[i] <= 10^4

输出说明 :

输出一行两个整数表示结果，整数间用空格隔开。第一个表示重复出现的整数，第二个表示丢失的整数。

输入范例 :

5
1 1 3 4 5

输出范例 :

1 2 

可能数组的编码 和序号套中套 有点难以理解 其实简单来说 也用了哈希表的知识（用了一个辅助数组haxiarr来记录 数据和他的arr下标记）

下面是正确的AC代码

#include<iostream>
#include<algorithm>
using namespace std;struct haxi
{int total = 0;int data1 = 0;int data2 = 0;int number1 = 0;int number2 = 0;
};
bool cmp(haxi x, haxi y)
{return x.total > y.total;
}
int main()
{int n = 0;cin >> n;int arr[10001];haxi haxiarr[10001];for (int i = 0; i < n; i++){cin>>arr[i];if (haxiarr[arr[i]].total > 0){haxiarr[arr[i]].data2 = arr[i];haxiarr[arr[i]].number2 = i;haxiarr[arr[i]].total++;}else{haxiarr[arr[i]].data1 = arr[i];haxiarr[arr[i]].number1 = i;haxiarr[arr[i]].total++;}}sort(haxiarr, haxiarr + 10000, cmp);if (haxiarr[0].data2 < arr[haxiarr[0].number2 - 1])//情况举例//1 1 3 4 5{cout << haxiarr[0].data1 << " ";cout << ++arr[haxiarr[0].number2 - 1] << " ";}else if(haxiarr[0].data2>arr[haxiarr[0].number2-1])//1 2 3 6 5 6 7 8 9 10{cout << haxiarr[0].data1 << " ";cout << ++arr[haxiarr[0].number1 - 1] << " ";}else if (haxiarr[0].data1 == arr[haxiarr[0].number2 - 1]){cout << haxiarr[0].data1 << " ";cout << ++haxiarr[0].data1 << " ";}return 0;}