寻找相同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不成立，那么将第一个数去掉，该题退化成上面一个题！
此思路值得借鉴！！！！
阅读(1433) | 评论(0) | 转发(0) |
