寻找相同 boj1329,1330 思想值得借鉴

寻找相同Submit: 1044   Accepted:263Time Limit: 1000MS  Memory Limit: 65535KDescription
有一组数，很多很多个数，里面有一个数出现了超过一半次，请你把它找出来。

Input
先是一个N (N<=400000)，然后接下来一行N个数，多组数据输入。

Output
对每个Case,输出一行，这一行只含有一个在之前数列中出现超过一半次的数。每个case之后输出一个空行。

Sample Input

11
5 5 5 5 5 5 1 2 3 4 6

Sample Output

Case 1: 5

解题思路：
这个题在编程之美上面有，方法是：创建一个栈，如果下一个数与当前的数一样，那么将下一个数入栈，否则pop出栈顶元素。最后留在栈里的元素即为结果



继续寻找相同Submit: 674   Accepted:123Time Limit: 2000MS  Memory Limit: 65535KDescription
有 n 个整数，其中有且仅有一个整数出现了 >= n/2.0 次 (n<=5000000)

Input
每组数据第一行是 n，然后接下来一行是 n 个整数。

Output
输出每行格式如A题

Sample Input

9
5 5 5 5 5 1 2 3 4


Sample Output

Case 1: 5

解题思路：
注意这个题的条件有小小的不同， “>=n/2”而不是“>n/2”。下面是解题方法：
1.判断第一个数是否出现了>=n/2次。
2.如果1不成立，那么将第一个数去掉，该题退化成上面一个题！

此思路值得借鉴！！！！