过半元素查找算法O（n）

Question

在一个规模为N的数组A中，所谓过半元素就是出现次数大于N/2的元素，例如
3.3.4.2.4.4.2.4.4
有一个过半元素4
给出一个算法，如果过半元素存在，，就找出来，否则给出报告
[b]问题补充：[/b]
我已经解决掉了这个问题了，对于一楼的那个算法我没有什么探讨，但是个人觉得有点不符合，二楼用了一个map把所有数组里的元素都放进去，一个个数，时间复杂度先不说，空间复杂度就够高的啦，下面是我的答案：
[code="java"]
class halfElement{
public static int find(int[] a){
int sum=1;
int x=a[0];
for(int i=1;i<a.length;i++){
if(a[i]==x){
sum=sum+1;
}else{
sum=sum-1;
}
if(sum<0){
x=a[i];
sum=1;
}
}
System.out.println(sum);
return x;
}

public static void main(String args[]){

    int[] a={3, 3, 1, 2, 2, 2, 2, 4, 1};    
    int result=find(a);
    for(int i=0;i<a.length;i++){
        System.out.print(a[i]+",");
        }
        System.out.println();
    System.out.println(result);

}
}

[/code]

[b]问题补充：[/b]
昨天时间太匆忙了，没仔细看，我的算法的确有问题，非常感谢taopian 和etank的指点，但是我仍然比较想找出不借助任何数据结构，[b]原地[/b]找出过半元素的O(n)算法，对于两位提出的算法我其实一开始又考虑过，显然这是最基本的解决方法，但是如果能找到原地查找的算法何乐而不为呢？

Answer 1

首先我运行过lz的代码，答案是
[code="java"]
1
3,3,1,2,2,2,2,4,1,
2
[/code]
但是这个例子中有9个数，结果却找到了2，2只出现过4次，并没有超过半数，所以lz的这个算法有点问题

我的思路和taopian的一样，如果说时间复杂度是合格了的，关于空间复杂度最差情况下map的大小为n，但是如果可以提前得出没有过半数的结论就可以避免空间的浪费，所以我认为可以加一个限制，如果map的大小超过（n+1）/2，则表示没有过半的数；再就是考虑到遍历数组的问题，我觉得不必要完全遍历完数组才知道，次数最多的数如果也没有希望就肯定没有过半数了，所以对taopian的代码作了一点点改动
[code="java"]
public static void main(String[] args) throws Exception {

    int[] nums = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    int size = 0, max = 0;

    for (int i = 0; i < num.length; i++) {
        Integer sum = map.get(num[i]);
        if (sum == null) {
            map.put(num[i], 1);

            if (++size > (num.length + 1)/2) {
               System.out.println("No number match.");
            }

        } else {
            ++sum;
            if (sum > num.length / 2) {
                System.out.println(num[i]);
                return;
            } else {
                map.put(num[i], sum);

                if (max < sum) {
                    max = sum;
                    if ((max + (num.length - i -1)) <= num.length/2) {
                        System.out.println("No number match.");
                    }
                }

            }
        }
    }

    for (Integer key : map.keySet()) {
        System.out.println(key + " : " + map.get(key));
    }
}

[/code]