帮忙分析一个算法。

一个含N个整数的数组，其中一个元素出现次数 k>N/2，找出这个元素。限O(N)时间，O(1)空间。其实就是找数组中出现次数最多的那个元素，看到一篇帖子，调试了一把发现有问题，

http://hi.baidu.com/wzfxyer/blog/item/a16bec99e6b7700f6f068c69.html

public class FindKinN {
    public static void main(String[] args) {

        int[] a = {1,1,1,1,2,2,1,1,2,2,2,1};
        int count,cur,n;
        
         count = 0;
         cur = 0;
         n = a.length;
        for (int i = 0; i < n; i++)
        {
            if (count == 0) cur = a[i];
            if (cur == a[i]) 
                 count++;
            else
                 count--;
            
         }
        
         System.out.println("你要找的是:" + cur);
     }

}
//适用范围：必须有支配者，而且必须大于n/2。

调试了一把，发现算法有问题，修改如下：

public class FindKinN {
	public static void main(String[] args) {

		int[] a = { 4, 3, -1, 3, 4, 3, 5 };
		int count, cur, n;

		count = 0;
		cur = a[0];
		n = a.length;
		for (int i = 0; i < n; i++) {
			if (cur == a[i])
				count++;
			else {
				count--;
				if (count == 0){
					cur = a[i];
				}
			}

		}
		System.out.println("你要找的是:" + cur);
	}

}

到底对不对心里没有底，请高手帮忙分析一下。



我也感觉不对，因为我想在count--之后才能变成0，故可能前面不用判断了，我再加上，再看看有什么问题。

public class FindKinN {
	public static void main(String[] args) {

		int[] a = {4,3,-1,3,4,3,5,4,4,4,4,4,4};
		int count, cur, n;

		count = 0;
		cur = a[0];
		n = a.length;
		for (int i = 0; i < n; i++) {
			if (count == 0){
				cur = a[i];
			}
			if (cur == a[i])
				count++;
			else {
				count--;
				if (count == 0){
					cur = a[i];
				}
			}

		}
		System.out.println("你要找的是:" + cur);
	}

}

我实现了一个很笨的算法，无论是时间复杂度还是空间复杂度都超了，希望谁给我改正一下：

import java.util.HashMap;
import java.util.Map;

public class FindKinN {
	public static void main(String[] args) {
		 int[] array = {3,4,3,2,-1,3,3};  
		 System.out.println(search(array));
	}
	public static int search(int[] array){
		Map<Integer,Integer> map  = new HashMap<Integer,Integer>();
		for(int i =0; i < array.length; i++){
			Integer value = map.get(array[i]);
			if(value == null){
				map.put(array[i], 1);
			} else {
				map.put(array[i], value + 1);
			}
		}
		int maxValue = -1;
		int maxKey = -1;
		for(Map.Entry<Integer, Integer> entry : map.entrySet()){
			int nextValue = entry.getValue();
			if(nextValue > maxValue){
				maxValue = nextValue;
				maxKey = entry.getKey();
			}
		}
		return maxKey;
	}
}

评论

2 楼 asialee 2009-03-17  

nerain 写道

你修改之后的：
int[] a = {4,3,-1,3,4,3,5,4,4,4,4,4,4}; 的话就不对了

我修改之后的代码不知道对不对，我已经不知道我的代码是干什么的了。
请帮忙分析一下。

1 楼 nerain 2009-03-17  

你修改之后的：
int[] a = {4,3,-1,3,4,3,5,4,4,4,4,4,4}; 的话就不对了