算法-找数组中出现次数超过一半的数

Dear 丶 2024-04-18 08:15 57阅读 0赞

## 1. 找出数组中出现次数超过一半的数 ##

给定数组，要求找出数组中出现次数超过数组长度一半的数。

## 2. 解法： ##

*  方法一：先将数组中的元素排序，由于目标元素的数量超过数组长度的一半，故排序后数组的中间元素(即数组的中位数)就是目标元素。  
    时间复杂度O(nlogn)
 *  方法二：构造一个HashMap，key为元素的值，value为元素出现的次数，然后遍历HashMap就可以找到目标元素了。  
    时间复杂度O(n)，空间复杂度为O(n)
 *  方法三：  
    思想：将一个目标元素和一个其它元素进行抵消，由于目标元素的数量大于其它元素的数量，故经过多次抵消后，剩下的元素即目标元素。  
    步骤：
    
        1)在遍历数组的时候保存两个值：数组中的一个元素(target) 和 该元素出现的次数(times)。
         2)当遍历到下一个元素的时候，如果下一个元素和我们之前保存的元素相等，则次数加1。
         3)如果下一个元素和我们之前保存的元素不相等，则次数减1。
         4)如果次数为零，需要保存下一个元素，并且把次数重设为1。
         5)由于目标元素出现的次数比其它所有元素出现的次数之和还要多，所以目标元素肯定是最终次数大于等于1时对应的元素。
          
          时间复杂度O(n)

public int moreThanHalfNum_Solution(int[] array) {
        
            int result = array[0]; // 记录候选值
            int count = 1; // 记录候选值出现次数,为 0 则更新候选值
    
            for (int i = 0; i < array.length; i++) {
        
                if (count == 0) {
        
                    result = array[i];
                    count++;
                } else if (result == array[i]) {
        
                    count++;
                } else {
        
                    count--;
                }
            }
            return result;
        }