11 wrong set

11  The wrong set

author : Turbo The time limit : 1S chapter :  curriculum design

Problem description :

aggregate s Contains from 1 To n The integer of , And in ascending order . Unfortunately , Because of the wrong data , Causes one number in the set to be copied to another number in the set , Results in a collection Lost a number also There's a number that repeats .

Given an array nums For the assembly S The result of an error .

Please find out the repeated integers , And find the missing integer .

Example 1：

Input ：

4

1 2 2 4

Output ：

2 3

Example 2：

Input ：

2

1 1

Output ：

1 2

Enter description :

Enter two lines ：

The first line is an integer n Representative array nums The length of .

Second line input n An integer represents an array nums The elements of .

Tips ：

    2 <= n <= 10^4

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

The output shows that :

Output a line of two integers to represent the result , Integers are separated by spaces . The first represents a recurring integer , The second represents the missing integer .

Input example :

5
1 1 3 4 5

Output example :

1 2 

Possible array encoding And serial number set in set It's a little hard to understand In fact, to put it simply Also used the knowledge of hash table （ An auxiliary array is used haxiarr To record Data and his arr Put a mark on ）

The following is true AC Code

#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])// For example 
															//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;

}