数字之魅——寻找发帖水王

淩亂°似流年 2022-08-02 15:50 180阅读 0赞

寻找发帖水王这个题目给了我很大的启发，同时开阔了视野，往往在解决这类型问题的时候第一想法都是先排序再计算。而本题却给出了一个非常好的思路，时间复杂度为O(N)。

它还有一个扩展问题，但是我在网上看了几篇有的写的考虑不周全，有的写的逻辑不是很清楚，这里我也根据思考和查阅，给出我自己的解法。

typedef int Type; //给出Id的一个抽象
    Type candidate[3] = {
       0}; //说明传的这个参数前要初始化。
    void find3(Type* ID,int N,Type* candidate){
        int i;int nTimes[3] = {
       0};
        for(i=0;i<N;i++){
            if(nTimes[0] == 0){
                if(candidate[1] == ID[i]){
                    nTimes[1]++;continue;
                }
                else if (candidate[2] == ID[i]){
                    nTimes[2]++;continue;
                }
                candidate[0] = ID[i];
            }
            else if(nTimes[1] == 0){
                if(candidate[0] == ID[i]){
                    nTimes[0]++;continue;
                }
                else if (candidate[2] == ID[i]){
                    nTimes[2]++;continue;
                }
                candidate[1] = ID[i];
            }
            else if(nTimes[2] == 0){
                if(candidate[0] == ID[i]){
                    nTimes[0]++;continue;
                }
                else if (candidate[1] == ID[i]){
                    nTimes[1]++;continue;
                }
                candidate[2] = ID[i];
            }
            else if(candidate[0] == ID[i])
                nTimes[0]++;
            else if(candidate[1] == ID[i])
                nTimes[1]++;
            else if(candidate[2] == ID[i])
                nTimes[2]++;
            else{
                nTimes[0]--;
                nTimes[1]--;
                nTimes[2]--;
            }
        }
    }

这里我采用参数了作为返回值结果，一方面因为很多时候会出现下面这种情况：

Type* find3(Type* ID,int N){
        //...
        int candidate[3] = {
       0};
        //...
        return candidate;
    }

这样函数退出结果就没有了，candidate指向了栈的某个未知区域了。  
或者  
Type\* find3(Type\* ID,int N)\{  
//…  
int\* candidate = new int\[3\];  
//…  
return candidate;  
\}  
在find3中new，但是在哪里去释放呢。我还是比较喜欢在哪里new就在哪里delete。  
最后，在判断nTimes\[0\] == 0的时候还要判断ID\[i\]与其他candidate是否相等的情况，所以我要求candidate要先初始化。