剑指Offer FindNumberMoreThanHalf 找出数组中出现次数超过一半的数字

谁借莪１个温暖的怀抱￠ 2022-06-10 12:18 113阅读 0赞

题目描述:

数组中有一个数字出现次数【超过 不会等于】数组长度的一半，请找出这个数字

思路：

1.  先对数组进行排序，出现次数超过一半的数组元素一定是该数组的中位数  
    这里使用效率比较好的双指针快排

/** * 基于快排算法 */
        public static int findNumberBySort(int[] array) {
            if (array == null || array.length == 0) {
                return -1;
            }
            //获取第一轮排序后 排序好元素的最终下标
            int resultIndex = partition(array, 0, array.length - 1);
            //中位数下标
            int middleIndex = array.length / 2;
            while (resultIndex != middleIndex) {
       //一直循环到找到中位数
                if (resultIndex < middleIndex) {
       //比中位数小
                    resultIndex = partition(array, resultIndex + 1, array.length - 1);
                } else {
       //比中位数大
                    resultIndex = partition(array, 0, resultIndex - 1);
                }
            }
    
            //检查中位数元素出现次数是否满足数组长度的一半
            if (checkNumCount(array, array[resultIndex])) {
                return array[resultIndex];
            } else {
                return -1;
            }
        }
     /** * 检查元素是否在数组中出现次数超过一半 * * @param array 数组 * @param result 目标元素 * @return true/false */
        private static boolean checkNumCount(int[] array, int result) {
            int count = 0;
            for (int i = 0; i < array.length; i++) {
                if (array[i] == result) {
                    count++;
                }
            }
            return count >= array.length / 2;
        }
    
        /** * 双指针快排 */
        private static int partition(int[] array, int start, int end) {
            if (start >= end) {
                return -1;
            }
            int base = array[start];
            int leftIndex = start;
            int rightIndex = end;
            while (leftIndex != rightIndex) {
                while (leftIndex < rightIndex && array[rightIndex] >= base) {
                    rightIndex--;
                }
                while (leftIndex < rightIndex && array[leftIndex] <= base) {
                    leftIndex++;
                }
                if (leftIndex < rightIndex) {
                    int temp = array[leftIndex];
                    array[leftIndex] = array[rightIndex];
                    array[rightIndex] = temp;
                }
            }
    
            array[start] = array[leftIndex];
            array[leftIndex] = base;
    
            return leftIndex;
        }

2.不使用排序的话 还可以根据由于该元素在数组中出现的次数大于一半，因此我们可以知道该元素出现的次数只和会大于其余元素出现次数的总和。  
因此我们可以用一个变量count来计数，一个变量result用来标识最小元素的值。首先result为第一个元素的值，count初始值为1，遍历数组，如果count为0的话，证明之前的元素中出现最多的元素出现的次数和其余元素出现次数和抵消，从当前元素开始重新计算，即result设置为当前元素，count重新设置为1，如果count不为0的时候再进行判断，如果当前元素不等于result，那么count自减，否则count自增。

注意数组中有可能出现没有元素出现的次数超过数组的一半，因此最后需要进行判断

public static int findNumberByCount(int[] array) {
            if (array == null || array.length == 0) {
                return -1;
            }
            int result = array[0];
            int count = 1;
            for (int i = 1; i < array.length; i++) {
                if (count == 0) {
       //如果count为0 则把result设置为当前元素 count设置为1
                    result = array[i];
                    count = 1;
                } else if (array[i] == result) {
       //如果当前元素和result相同 count+1
                    count++;
                } else {
                    count--;
                }
            }
            if (checkNumCount(array,result)){
                return result;
            }else{
                return -1;
            }
        }

测试：

@RunWith(Parameterized.class)
    public class FindNumberMoreThanHalfTest { 
    
        @Parameterized.Parameters
        public static List<Object[]> data(){
            List<Object[]> data = new ArrayList<>();
            data.add(new Object[]{
       new int[]{
       1,2,3,2,2,2,5,4,2}, 2});
            data.add(new Object[]{
       new int[]{
       1,2,3,6,8,5,5,4,2}, -1});
            data.add(new Object[]{
       null,-1});
            return data;
        }
    
        private final int[] array;
        private final int max;
    
        public FindNumberMoreThanHalfTest(int[] array, int max) {
            this.array = array;
            this.max = max;
        }
    
        @Test
        public void testFindBySort() throws Exception {
            int result = FindNumberMoreThanHalf.findNumberBySort(array);
            assertEquals(max,result);
        }
    
        @Test
        public void testFindByCount() throws Exception {
            int result = FindNumberMoreThanHalf.findNumberByCount(array);
            assertEquals(max,result);
        }
    
    }

--------------------