多数元素

题目要求

给定一个大小为 n 的数组 nums，要求找出并返回这个数组中的“多数元素”。所谓“多数元素”，是指在数组中出现次数超过 n/2 的元素（这里的 n 是数组的长度）。题目假设条件为数组非空，并且保证一定存在一个多数元素。

解题思路

要解决这个问题，我们可以采用几种不同的方法：

哈希表法：遍历数组，使用哈希表记录每个元素出现的次数，然后再次遍历哈希表，找到出现次数大于 n/2 的元素。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)。
排序法：将数组排序，由于多数元素的数量超过 n/2，因此排序后位于中间位置的元素（即索引为 n/2 的元素）一定是多数元素。这种方法的时间复杂度为 O(nlogn)，因为排序通常需要 O(nlogn) 的时间，空间复杂度取决于所使用的排序算法。
摩尔投票法：这是一种时间复杂度为 O(n) 且空间复杂度为 O(1) 的高效算法。算法的基本思想是维护一个候选多数元素和一个计数器，初始化时计数器为 0。遍历数组，对于每个元素，如果计数器为 0，则将当前元素作为候选多数元素，计数器设置为 1。如果计数器不为 0，当遇到与候选多数元素相同的元素时，计数器加 1，否则减 1。由于多数元素的数量超过了数组长度的一半，因此最后候选的元素一定是多数元素。
随机化：由于多数元素的数量超过了数组长度的一半，我们可以随机选取一个元素，然后检查它是否是多数元素，这样做的期望时间复杂度是 O(n)，但最坏情况下可能会达到无限大，因为可能需要无限次随机尝试才能找到多数元素。

在实际应用中，摩尔投票法因其优秀的时间和空间复杂度表现通常是最佳选择。

Golang 版本

package main

import "fmt"

func majorityElement(nums []int) int {
    candidate := nums[0]
    count := 1

    // 摩尔投票法
    for _, num := range nums[1:] {
        if count == 0 {
            // 更换候选人
            candidate = num
            count = 1
        } else if candidate == num {
            // 候选人计数加一
            count++
        } else {
            // 非候选人计数减一
            count--
        }
    }

    // candidate 即为多数元素
    return candidate
}

func main() {
    nums := []int{2, 2, 1, 1, 1, 2, 2}
    fmt.Println("多数元素是：", majorityElement(nums))
}

这段代码实现了摩尔投票法，用于找出给定数组中的多数元素。在主函数 main 中，我们定义了一个数组 nums 并调用 majorityElement 函数来找出并打印多数元素。

C++版本

#include <iostream>
#include <vector>

int majorityElement(std::vector<int>& nums) {
    int count = 0;
    int candidate = 0;

    // 使用摩尔投票法
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

int main() {
    std::vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
    std::cout << "多数元素是：" << majorityElement(nums) << std::endl;
    return 0;
}

这段 C++代码同样实现了摩尔投票法，用于找出给定数组中的多数元素。在 main 函数中，我们定义了一个 vector 类型的数组 nums 并调用 majorityElement 函数来找出并打印多数元素。

Python 版本

def majority_element(nums):
    count = 0
    candidate = None

    # 使用摩尔投票法
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)

    return candidate

# 测试代码
if __name__ == "__main__":
    nums = [2, 2, 1, 1, 1, 2, 2]
    print("多数元素是：", majority_element(nums))

Java 版本

public class MajorityElement {
    public static int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("多数元素是：" + majorityElement(nums));
    }
}

这段 Java 代码实现了摩尔投票法，用于找出给定数组中的多数元素。在 main 方法中，我们定义了一个数组 nums 并调用 majorityElement 方法来找出并打印多数元素。

Rust 版本

fn majority_element(nums: Vec<i32>) -> i32 {
    let mut count = 0;
    let mut candidate = nums[0];

    for &num in nums.iter().skip(1) {
        if count == 0 {
            candidate = num;
        }
        if num == candidate {
            count += 1;
        } else {
            count -= 1;
        }
    }

    candidate
}

fn main() {
    let nums = vec![2, 2, 1, 1, 1, 2, 2];
    println!("多数元素是：{}", majority_element(nums));
}

这段 Rust 代码实现了摩尔投票法，用于找出给定向量中的多数元素。在 main 函数中，我们定义了一个向量 nums 并调用 majority_element 函数来找出并打印多数元素。

总结

上述代码示例中，无论是 Golang、C++、Python 还是 Java 和 Rust 版本，核心算法都是基于摩尔投票法（Boyer-Moore Voting Algorithm）。这个算法的基本思想是通过一系列的对消过程，找到那个出现次数超过数组长度一半的元素，即“多数元素”。

摩尔投票法的步骤如下：

初始化一个候选多数元素 candidate 和一个计数器 count 为 0。
遍历数组中的每个元素 num：
- 如果 count 为 0，将 num 设为 candidate。
- 如果 num 等于 candidate，则 count 加一。
- 如果 num 不等于 candidate，则 count 减一。
遍历完成后，candidate 即为多数元素。

这种算法的优势在于它的空间复杂度为 O(1)，即只需要常数级别的额外空间。时间复杂度为 O(n)，因为它只需要遍历数组一次。这使得摩尔投票法成为解决这类问题的一个高效算法。

在实际代码实现中，各种语言的语法有所不同，但算法的核心逻辑是一致的。例如，在 Rust 中使用 iter() 和 skip() 来遍历数组，而在 Python 中则直接使用 for 循环。尽管实现细节不同，但所有版本的代码都遵循了摩尔投票法的基本原则，成功地解决了寻找多数元素的问题。

hot-100