剑指Offer Java版 面试题39：数组中出现次数超过一半的数字

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

练习地址

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163

解法一：基于Partition函数的时间复杂度为O(n)的算法

public class Solution {
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int middle = array.length >> 1, start = 0, end = array.length - 1;
        int index = partition(array, start, end);
        while (index != middle) {
            if (index > middle) {
                end = index - 1;
            } else {
                start = index + 1;
            }
            index = partition(array, start, end);
        }
        int result = array[middle], times = 0;
        for (int number : array) {
            if (number == result) {
                times++;
            }
        }
        return times > array.length >> 1 ? result : 0;
    }
    
    // 基于《算法（第4版）》的快速排序算法代码
    private int partition(int[] a, int lo, int hi) {
        if (lo == hi) {
            return lo;
        }
        int i = lo, j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (v < a[--j]) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
    
    private void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

解法二：根据数组特点找出时间复杂度为O(n)的算法

public class Solution {
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int result = 0, times = 0;
        for (int number : array) {
            if (times == 0) {
                result = number;
                times = 1;
            } else if (number == result) {
                times++;
            } else {
                times--;
            }
        }
        times = 0;
        for (int number : array) {
            if (number == result) {
                times++;
            }
        }
        return times > array.length >> 1 ? result : 0;
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题