一道java面试题

题目：
一个数组，“支配者”是在数组中出现频率超过一半的整数，
例如[3,4,3,2,-1,3,3,3]数值“3”出现过5次，5除以8大于0.5
所以数值“3”是一个支配者；
而在这个数组中的支配者出现在数组下标[0,2,4,6,7]
写一个函数，在给定的整数数组中找出支配者所在的任意一个数组下标，如果一个数组中没有支配者返回-1；

 

解决代码如下：

public class ArrayOperate {
    static List<Integer> find(int[] a) {
        int length = a.length;
        int half = length / 2;
        int count = 0;
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (a[i] == a[j]) {
                    list.add(j);
                    count++;
                }
            }
            if (count > half) {
                break;
            } else {
                count = 0;
                list.clear();
            }
        }
        if (list.size() == 0) {
            list.add(-1);
        }
        return list;
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,2,2,6,2,8,2,2};
        int [] b = {2,1,2,1,1,3,1,1,2,2,2,1};
        List<Integer> result = find(b);
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

 

 

评论

3 楼 JohnnyJian 2008-12-03  

用hashmap就好啦

2 楼 ganglong99 2008-12-03  

有什么好的方法吗？
降低一下复杂度。

1 楼 JohnnyJian 2008-12-03  

O(n^2)的复杂度太高了……