SOJ--4389: 川大貼吧水王

SOJ--4389: 川大貼吧水王

描述

_L的室友HZ喜歡在川大貼吧上發帖，據傳說，HZ在川大貼吧上發的貼子數已經超過了該貼吧貼子總數的一半，被江湖人封為川大貼吧水王，你能幫_L迅速找出這位川大貼吧水王HZ的ID嗎？
已知川大貼吧貼子總數為n，給出n個貼子作者的ID，求HZ的ID。
Input

輸入文件包含多組測試數據。第一行為測試的數據組數T(T<=40)。
接下有T組數據，第一行輸入貼子總數n(1<=n<=10000000),接下來的一行有n個正整數，分別為每位貼子作者的ID號(該ID號為不超過10^9的正整數)
Output

輸出T行，每行為該組測試數據的川大貼吧水王HZ的ID。
Example Input

2
3
1 2 2
5
1 2 3 3 3
Example Output

2
3
Author

_L

解析：常規來看，可以對輸入的id號進行排序，然後進行查找，但是看到總數n最大為10000000，猜想應該會超時，但是還是快速敲了代碼測試了下，結果果然超時，所以這個暴力方法是行不通的 貼一下自己超時代碼

#include
#include
using namespace std;
//定義存放數據的數組，設值為全局變量
const int M=10000000+5;
int a[M];
int main()
{
	int T;
	//輸入T組數據
	cin >> T;
	while(T--)
	{
		int n;
		cin >> n;
		//輸入數據
		for(int i=0; i> a[i];
		}
		//對輸入的數組進行排序
		sort(a,a+n);
		//找出現次數大於n/2的id號
		int cnt=1, value=a[0];
		for(int i=1; in/2)
				{
					cout << value << endl;
					break;
				}
			}else{
				value=a[i];
				cnt=1;
			}
		}
	}
	return 0;
}

然後再仔細看題進行分析，題目中有個重要的信息就是所找的id號出現的次數大於總次數的一半，可以利用這個原理進行優化代碼。 一次遍歷數組就可以得到，利用兩個變量 k 和 j 來保存中間的值，其中k保存每次比較的值，j 存放次數，遍歷數組，如果當前數組a[i]等於k則j++反而j--，也就是利用抵消的思想，因為最終要找的數出現的次數大於總數的一半，所以這個數的次數j最後一定是大於0的，也就是利用這個原理可以使復雜度降到O(n) 貼下AC代碼(注意不要用cin、cout)

#include
const int M=10000000+5;
int a[M];
int search(int A[], int length)
{
	int k, j=0;
	for(int i=0; i