找出整型数组占比超过一半的数

题目描述

小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

测试样例

样例1：

输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出：3

样例2：

输入：array = [5, 5, 5, 1, 2, 5, 5]
输出：5

样例3：

输入：array = [9, 9, 9, 9, 8, 9, 8, 8]
输出：9

解题思路

初始化哈希表：创建一个空的字典来存储每个数字及其出现次数。

遍历数组：对于数组中的每个数字，更新哈希表中该数字的出现次数。

查找目标数字：遍历哈希表，找到出现次数超过数组长度一半的数字。

返回结果：返回找到的数字。

代码实现

Cangjie

import std.collection.*

func solution(array: Array<Int64>) {
    let size = array.size
    var map = HashMap<Int64, Int64>(size, {i => (array[i], 0)})
    for(num in array) { map[num]++ }
    for((num, count) in map ) {
        if( count > size / 2) { return num }
    }
    0
}

main() {
    println(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)
}

摩尔投票算法 (Boyer–Moore majority vote)

import std.collection.*

// Boyer–Moore majority vote
func solution(array: Array<Int64>) {
    var (candidate, count) = (0, 0)
    let map = HashMap<Int64, Int64>(array.size, {i => (array[i], 0)})
    for (num in array) {
        match {
            case count == 0 => (candidate, count) = (num, 1)
            case candidate == num => count++
            case _ => count--
        }
        map[num]++
    }
    if (map[candidate] > array.size / 2) { candidate }
    else { 0 }
}

main() {
    println(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)
}

Rust

 use std::collections::HashMap;

fn solution(array: Vec<i64>) -> i64 {
    let size = array.len();
    let mut map = HashMap::new();
    for num in array {
        *map.entry(num).or_insert(0) += 1;
    }
    for (num, count) in map {
        if count > size / 2 {
            return num;
        }
    }
    0
}

 fn main() {
    println!("{}", solution(vec![1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3);
 }

Python

def solution(array):
    size = len(array)
    map = {}
    for num in array:
        map[num] = map.get(num, 0) + 1
    for num, count in map.items():
        if count > size / 2:
            return num
    return 0

print(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)

JavaScript

function solution(array) {
    const size = array.length;
    const map = {};
    for (let num of array) {
        map[num] = (map[num] || 0) + 1;
    }
    for (let [num, count] of Object.entries(map)) {
        if (count > size / 2) {
            return num;
        }
    }
    return 0;
}

console.log(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3);

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组一次来统计每个数字的出现次数。

空间复杂度：O(n)，其中 n 是数组的长度。需要使用哈希表来存储每个数字及其出现次数。

仓颉编程语言