数组中出现次数超过一半的数字

jiezi

5 年前

[TOC]

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。

代码

import java.util.HashMap;
import java.util.Map;
public class Solution {public int MoreThanHalfNum_Solution(int [] array) {
        int num = 0;

        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int len =  array.length ;
        if(len == 0) return 0;
        for(int i = 0; i < len ;i++){if(map.containsKey(array[i])){int count = map.get(array[i]);
                 ++count;
                map.put(array[i],count);
            }else{map.put(array[i],1);
            }
        }
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){if(entry.getValue() > (len/2)){num = entry.getKey();
            }

        }
        return num;
    }
}

总结

map 的遍历方式
使用 map 存储出现次数的映射关系
map.put(key,value)

由于出现次数超过一半，那么最中间的数一定是那个出现次数超过一半的数，也就是中位数

我们先用排序算法对该数组排序，若用快速选择排序，时间复杂度为 O(nlogn)

我们知道快速排序中，每次划分都是基于 partition 函数返回的 index 作为划分点，使得数组左边的数小于 arr[index], 数组右边的数大于 arr[index]

这里其实 partition 返回的 index 也就是数组 arr 中第 k 大数据的坐标索引

所以借鉴过来，本题需要求出现次数超过一半的数，那么实际上也就是中位数，即索引为 n / 2 的数，

就等同于求第 n / 2 大的数据

快速排序算法中我们是通过 partition 函数求出索引，本题我们是知道了索引，求具体的数据

那么我们就需要以 n / 2 为基准，使得左边的数小于 arr[n/2], 右边的数大于 arr[n/2]

实现

public class Solution {
    // 检测无效输入，如果数字的次数不超过长度的一半
    public boolean isValid(int[] arr,int numer){
        int count = 0;
        for(int i = 0; i < arr.length; i++){if(numer == arr[i]) count++;
        }
        if(count * 2 <= arr.length) return false;
        return true;
    }

    public void swap(int[] arr,int i,int j){
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }

    public int partition(int[] arr,int low,int high){int base = arr[high];
        int i = low - 1;
        for(int j =low; j < high; j++){
            // 注意这里是小于等于
            if(arr[j] <= base){
                i++;
                swap(arr,i,j);
            }
        }
        swap(arr,i + 1,high);

        return i+1;
    }
    public int MoreThanHalfNum_Solution(int [] array) {if(array == null || array.length <= 0)return 0;
        int index = partition(array, 0, array.length - 1);
        int middle = (array.length - 1) >> 1;
        while (index != middle){if(index < middle){index = partition(array, index + 1, array.length - 1);
            }else {index = partition(array, 0, index - 1);
            }
        }
        boolean flg = isValid(array, array[middle]);
        if(!flg) return 0;
        return array[middle];
    }
}

该思路的时间复杂度：平均时间复杂度为 O(n * logn/2) = O(nlogn), 如果一次性就能找到 n / 2 的下标，那么时间复杂度可以达到 o(n)

但是该算法的缺点在于修改了原数组

由于有个数字出现的次数超过数组长度的一半，那么也就是说它出现的次数比其他数字出现的次数之和还要多，如果我们将数组中的数字两两同或（相同为 1，相异为 0）那么两两抵消之后，最后只会剩下这个出现出现次数超过一半的数字，那么我们如何实现这个同或抵消的过程呢

首先我们需要保存当前正在读取的数，还有当前数字出现的次数，如果下一个数字和当前数字不相同，那么当前数字的次数就减 1，

public class Solution {public boolean isValid(int[] arr,int numer){
        int count = 0;
        for(int i = 0; i < arr.length; i++){if(numer == arr[i]) count++;
        }
        if(count * 2 <= arr.length) return false;
        return true;
    }
    public int MoreThanHalfNum_Solution(int [] array) {if(array == null || array.length <= 0) return 0;
        int cur = array[0];
        int count = 1;
        int res = array[0];// 初始化为 array[0] 有可能第一个数就是返回值
        for(int i = 1; i < array.length; i++){if(cur != array[i] ){if(count != 0){count--;}else {
                    count = 1;
                    res = array[i];
                }
                cur = array[i];
            }else {count++;}

        }
        boolean flg = isValid(array, res);
        if(!flg) return 0;
        return res;
    }
}

该算法的时间复杂度为：O(n)

《剑指 offer 纪念版》

数组中出现次数超过一半的数字

题目描述

思路一：利用 map 统计每个数字出现的次数

思路二：先对数组进行排序，然后取出 arr[n/2]

思路三：基于 partition 函数的 O(n) 的算法

思路四：根据数组特点找出 O（n）的算法

参考