Chapter3: 更好的查找与排序算法

7. 实战解题：哪个数字重复数超过了数组一半长度？

题目

数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

算法

分析：因为这个数字k出现次数超过了N/2，注意利用这个特性这意味着：

• 如果数组排好序的话，第N/2个元素一定是这个数字
• 这个数k的出现次数比所有其它元素加起来的还要多。

解法1

思路

hash统计，hashmap 没学，之后再说

解法2

思路

排序后返回arr[N/2] ，时间复杂度为快排的时间复杂度 O(nlgn)

解法3

思路

与上一题找k类似，其实不需要将全部数组排好序，进行一次快排的划分即可，此时 arr[N/2] 即为所求的数， 时间复杂度为 O(n)

快排的双向扫描分区法的代码参考上一篇文章

解法4

思路

如果一个数出现的次数超过数组一半的长度，那么就是说出现的次数比其他所有数字出现的次数还要多。

• 设置2个变量 value 和 count ，value 代表元素的值，初始化为第一个元素值，count 代表某元素值的出现次数，初始化为1

• for循环遍历数组，如果下一个元素的值与 value 的值相同,则 count++ ，否则count-- , 当count==0 时，将value 设置为下一个元素值并将count值设为1

  当count==0时，网上的代码都是跳过了与 value使之为0的那个数，将下下位赋值给 value 的

  比如数组里第一个数和第二个数不同的话，按照网上代码的走法就会跳过第二个值，强迫症的我感觉每个元素都要赋值给 value 比较过才对，只需在 if(count==0) 的条件下，i-- 回退一位即可

  至于为什么跳过也可以，以"第2个元素与第1个元素不同"这种情况来说，第2个元素使得 count变为0,即相当于第2个元素与第1个元素对消，如果按照网上的代码跳过了第2个元素

  • 如果第2个元素是其它元素，则对结果没有影响；
  • 如果第2个元素就是要找的元素，因为要找的元素 k 数量是大于N/2的，所以就算刚好只有[N/2]+1个，并且其它元素与 k一一对消 ,与也会剩下一个k，所以跳过对结果没有影响

  debug的过程真是艰辛啊┭┮﹏┭┮

• 因为要找的数字出现的次数比其他所有的数字出现的次数之和要大，所以遍历完数组，最后必然count>=1， 并且 value 的值就是要找的值

代码

int findK(int* arr,int arrLen){
    int value=arr[0];
    int count=1;
    for(int i=1;i<arrLen;i++){

        if(count==0){
            i--;//避免value的赋值跳过那个使count等于0的与value比较的数组元素 ,网上其它人的代码就是少了这条语句
            value=arr[i];
            count++;
        }

        else{
            if(value==arr[i])//count!=0 && value==arr[i] 
                count++;
            else//count!=0&value!=arr[i]
                count--;
        }
    }
    return value;
}

debug过程记录

一开始发现网上的代码是跳过之后，也没有仔细思考可行性，就试着验证一下把第2个元素设置为要找的值 k ，结果出错了，找了另一个出现次数比 k 少1次的数，就以为自己的想法是正确的，因为跳过了一个k 值

于是就额外写了个判断语句，使得不跳过第二个数，运行结果就正确了，科十自己又想，跳过也不是只是第二个数跳过啊，自己在脑海里演练了一下，发现使得 count==0 的那个数组元素在赋值给 value 时都会被跳过，这就说不通了，那就应该在if(count==0) 里面改，改了又有bug!!

在网上找了两篇博客，这一思路的写法都是那样跳过的，但是验证又有问题，差点要放弃，找第三篇博客的时候， 看到别人还写了验证输入数组是否存在数量超过长度一般的数的代码，忽然发现自己之前自己设置的数组中重复数最高的数没有超过数组长度的一半！！所以才会报错！于是把数组修正过来，网上的代码就不报错了！但是自己的代码还是有错，正百思不得其解的时候忽然想到 value=arr[i--]; 这种写法是先赋值，i 再-1，修正为 [--i] 就没问题了

扩展：加强版水王问题

问题

我们知道，水王问题：有N个数，其中有一个数出现超过一半，要求在线性时间求出这个数。(就是上面解决的问题)

加强版水王：有N个数，其中有一个数刚好出现一半次数，要求在线性时间内求出这个数。

思路

仔细分析的话，占一半的数字，只能在两个变量中出现：value 和数组最后一个元素arr[arrLen-1]。只需要在遍历数组的时候统计最后一个变量arr[arrLen-1] 的出现次数即可，如果=arrLen/2 ，则它就是要找的元素，否则 value 就是

代码

int findK(int* arr,int arrLen){
    int value=arr[0];
    int count=1;
    int countOfLast=0;//统计最后的元素arr[n-1]出现的个数 
        
    for(int i=1;i<arrLen;i++){
        
        //增加最后一个元素的计数步骤
        if(arr[i]==arr[arrLen-1]) 
            countOfLast++;
        
        if(count==0){
            i--;//避免value的赋值跳过那个使count等于0的与value比较的数组元素 
            value=arr[i];
            count++;
        }

        else{
            if(value==arr[i])//count!=0 && value==arr[i] 
                count++;
            else//count!=0&value!=arr[i]
                count--;
        }
    }
    
    //增加最后一个元素的计数步骤
    if(arr[0]=arr[arrLen-1])
        countOfLast++;
    //如果最后一个元素出现次数是n/2,则这个元素就是要找的数 
    if(countOfLast==arrLen/2)
        return arr[arrLen-1];
    else
        return value;
}

参考资料

[1] 一个数组中有一个数字的次数超过了数组的一半

[2] 加强版水王：找出出现次数刚好是一半的数字

l