重复元素问题

Question

一道笔试题，时间复杂度要求O(N)
int数组中有三个元素出现的次数超过元素总个数的1/4,在规定时间复杂度下，求出这三个数。
我的思路，交卷的一刹那，我发现自己考虑非常不全面。
定义三个变量，保存三个数，在定义三个计数器，开始把a[0],a[1],a[2]赋给三个变量（这里有问题，万一重复了），然后对后面的数组扫描，出现相等的计数器加一，不相等计数器减一。

已经通知下午2点面试，晚上再跟大家探讨下，这题其实跟数组中有元素超过数组一半是一类问题吧，可能考虑起来要复杂点。

请用C/C++实现，Java我不熟。

Answer 1

//多谢@ zonxin @brayden 这是编程之美 寻找发帖水王扩展问题，代码如下，参考网址

void find3(int * ID, int n)
{
    int candidate[3];
    int nTimes[3] = {0};
    int i;
    for (i = 0; i < n; i++)
    {
        if(nTimes[0] == 0)
        {
            if(ID[i] == candidate[1])
                nTimes[1]++;
            else if (ID[i] == candidate[2])
                nTimes[2]++;
            else
                {
                    candidate[0] = ID[i];
                    nTimes[0]++;
                }
        }
        else if (nTimes[1] == 0)
        {
            if(ID[i] == candidate[0])
                nTimes[0]++;
            else if (ID[i] == candidate[2])
                nTimes[2]++;
            else
                {
                    candidate[1] = ID[i];
                    nTimes[1]++;
                }
        }
        else if (nTimes[2] == 0)
        {
            if(ID[i] == candidate[0])
                nTimes[0]++;
            else if (ID[i] == candidate[1])
                nTimes[1]++;
            else
            {
                candidate[2] = ID[i];
                nTimes[2]++;
             }
        }
        else
       {
            if(ID[i] == candidate[0])
                nTimes[0]++;
            else if(ID[i] == candidate[1])
                nTimes[1]++;
            else if(ID[i] == candidate[2])
                nTimes[2]++;
            else
                nTimes[0]--, nTimes[1]--, nTimes[2]--;
        }
    }
printf("三个水王ID分别是:%d,%d,%d\n", candidate[0], candidate[1], candidate[2]);
}

Answer 2

用Java写了一个，应该不是很准确。

使用c语言的话原理是一样的，也是使用哈希表来实现，只是C语言不好定义哈希的大小。

我的代码

import java.util.*;

/**
 * Created by Nicholas on 2015/10/11.
 */
public class Soluction {

    /**
     * @brief 使用hashmap，时间复杂度是O(N),空间复杂度是O(n)
     * @param data 目标数组
     * @return list结果
     */
    public static List<Integer> getNumbers(int[] data){
        List<Integer> result = new ArrayList<>();
        if(data==null || data.length<=4)
            return result;
        Map<Integer,Integer> map = new HashMap<>();
        /**
         * 使用hashmap,其中的key是数组中元素的值，value是出现的次数
         * 当检测到已经出现key时，将key的value加一
         */
        for(int i = 0;i<data.length;i++){
            if(map.containsKey(data[i]))
                map.put(data[i],map.get(data[i])+1);
            else
                map.put(data[i],1);
        }
        int critical = data.length/4;
        /**
         * 遍历这个hashmap,找出value大于1/4 总大小的 key
         */
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue()>critical)
                result.add(entry.getKey());
        }
        return result;
    }

    public static void main(String[] args) {
       int[] data = {1,1,1,1,2,2,2,2,3,3,3,3,4,5,6};
        List<Integer> result = Soluction.getNumbers(data);
        for (Iterator<Integer> iter = result.iterator();iter.hasNext();){
            System.out.println(iter.next());
        }
    }
}