数组中超过一半的数字

1. 来源

• 剑指offer-面试题39
• LeetCode169 https://leetcode.com/problems/majority-element/

2. 题目描述

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

3. 题目分析3种解法

很多应聘者会想到如果是排好序的数组，那么超过数组长度一半的数字肯定是中位数。此时时间复杂度为。有没有更好的时间复杂度为的算法呢？

• 解法一：使用字典进行统计每个元素出现的频次，判断频次超过数组长度一半的数字即为答案。(字典法)

• 解法二：根据数组特点，也就是说它出现的次数比其他所有数字出现的次数之和还要多。因此，我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是次数。当我们遍历数组到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字跟我们之前保存的数字不同，则次数减1。如果次数为0，那么我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设置为1时对应的数字。(开枪法)

• 解法三：这种算法受到快速排序算法启发。在随机快速排序算法中，我们先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是，那么这个数字就是数组的中位数；如果它的下标大于，那么中位数应该位于它的左边，我们可以接着在它的左边部分数组中查找；如果它的下标小于，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程。(快排法)

4. 程序实现

1. Java编码实现

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    // 使用HashMap字典
    public static int moreThanHalfNum(int[] numbers) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for(int num : numbers) {
            if(numMap.containsKey(num)) {
                numMap.put(num, numMap.get(num) + 1);
            } else {
                numMap.put(num, 1);
            }
            // 超过数组长度一半的数字
            if(numMap.get(num) > numbers.length / 2) {
                return num;
            }
        }
        return 0;
    }

    // 基于快排的思想
    public static int quickSelect(int[] numbers, int l, int r, int k) {
        // 递归终止条件
        if(l >= r) {
            return numbers[l];
        }
        int pivot = numbers[r];
        int left = l;
        int right = r - 1;
        while(left <= right) {
            while(left <= right && numbers[left] < pivot) {
                left++;
            }
            while(left <= right && numbers[right] >= pivot) {
                right--;
            }
            if(left > right) {
                break;
            }
            // swap numbers[left] with numbers[right] while left <= right
            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
        }
        // swap the smaller with pivot
        numbers[r] = numbers[left];
        numbers[left] = pivot;

        if(left == k) {
            return numbers[k];
        } else if(left > k) {
            return quickSelect(numbers, l, left - 1, k);
        } else {
            return quickSelect(numbers, left + 1, r, k);
        }

    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println("方法一-->超过数组长度一半的数字：" + moreThanHalfNum(numbers));
        System.out.println("方法二-->超过数组长度一半的数字：" + quickSelect(numbers, 0, numbers.length - 1, numbers.length / 2));
    }

}

# 结果
方法一-->超过数组长度一半的数字：2
方法二-->超过数组长度一半的数字：2

2. Python编码实现

class Solution(object):
    
    # 使用字典统计
    def moreThanHalfNum(self, numbers):
        numbers_dict = {}
        for num in numbers:
            if num in numbers_dict:
                numbers_dict[num] += 1
            else:
                numbers_dict[num] = 1
            # 超过一半的数字
            if numbers_dict[num] > len(numbers) // 2:
                return num
        return 0

    # 开枪法(得到的是其中一个整体靠后的众数)
    def moreThanHalfNum2(self, numbers):
        if not numbers:# 空列表
            return 0
        num = numbers[0]
        counter = 1
        for item in numbers:
            if num == item:
                counter += 1
            else:
                counter -= 1
            if counter == 0:
                num = item
                counter = 1
        
        # 判断最后得到的num的个数是否超过数组一半
        counter = 0
        for item in numbers:
            if item == num:
                counter += 1
        return num if counter > len(numbers) //2 else 0

    # 基于快排思想
    def quickSelect(self, numbers, l, r, k):
        if l >= r:
            return
        pivot = numbers[r]
        left, right = l, r - 1
        while left <= right:
            while left <= right and numbers[left] < pivot:
                left += 1
            while left <= right and numbers[right] >= pivot:
                right -= 1
            if left > right:
                break
            # swap numbers[left] with numbers[right] while left <= right
            numbers[left], numbers[right] = numbers[right], numbers[left]

        # swap the smaller with pivot
        numbers[left], numbers[r] = numbers[r], numbers[left]

        if left == k:
            return numbers[k]
        elif left > k:
            return self.quickSelect(numbers, l, left -1, k)
        else:
            return self.quickSelect(numbers, left + 1, r, k)


if __name__ == "__main__":
    numbers = [1, 2, 3, 2, 2, 2, 5, 4, 2]
    solution = Solution()
    print("方法一-->数组中超过一半的数字是：", solution.moreThanHalfNum(numbers))
    print("方法二-->数组中超过一半的数字是：", solution.moreThanHalfNum2(numbers))
    print("方法三-->数组中超过一半的数字是：", solution.quickSelect(numbers, 0, len(numbers) - 1, len(numbers) // 2))

# 结果
方法一-->数组中超过一半的数字是： 2
方法二-->数组中超过一半的数字是： 2
方法三-->数组中超过一半的数字是： 2

3. C++编码实现

#include <iostream>
#include <map>

class Solution
{
public:
    // 使用HashMap字典
    int moreThanHalfNum(int* numbers, int length) {
        std::map<int, int> numMap;
        for(int i = 0; i < length; i++) {
            if(numMap.count(numbers[i]) != 0) {
                numMap[numbers[i]]++;
            } else {
                numMap[numbers[i]] = 1;
            }
            // 超过数组长度一半的数字
            if(numMap[numbers[i]] > length / 2) {
                return numbers[i];
            }
        }
        return 0;
    }

    // 基于快排的思想
    int quickSelect(int* numbers, int l, int r, int k) {
        // 递归终止条件
        if(l >= r) {
            return numbers[l];
        }
        int pivot = numbers[r];
        int left = l;
        int right = r - 1;
        while(left <= right) {
            while(left <= right && numbers[left] < pivot) {
                left++;
            }
            while(left <= right && numbers[right] >= pivot) {
                right--;
            }
            if(left > right) {
                break;
            }
            // swap numbers[left] with numbers[right] while left <= right
            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
        }
        // swap the smaller with pivot
        numbers[r] = numbers[left];
        numbers[left] = pivot;

        if(left == k) {
            return numbers[k];
        } else if(left > k) {
            return quickSelect(numbers, l, left - 1, k);
        } else {
            return quickSelect(numbers, left + 1, r, k);
        }

    }

};

int main() {
    int numbers[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
    Solution solution;
    std::cout << "方法一-->超过数组长度一半的数字：" << solution.moreThanHalfNum(numbers, 9) << std::endl;
    std::cout << "方法二-->超过数组长度一半的数字：" << solution.quickSelect(numbers, 0, 8, 4) << std::endl;

    return 0;
}

# 结果
方法一-->超过数组长度一半的数字：2
方法二-->超过数组长度一半的数字：2

4. Go编码实现