leetcode169：多数元素

题目链接

leetcode

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

void printArray(const vector<int>& arr) {
    for (const int& num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

/*
    哈希表，记录每个元素出现的次数

    时间复杂度：O(n)
        其中 n 是数组的长度。
        遍历数组一次。
    空间复杂度：O(n)
        哈希表占用的空间为 O(n)。
*/
class Solution_0 {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> num2cnt;
        int num, cnt = 0;
        for (const auto& x : nums) {
            num2cnt[x] ++;
            if (cnt < num2cnt[x]) {
                num = x;
                cnt = num2cnt[x];
            }
        }
        
        return num;
    }
};

/*
    把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0。
    因此，众数一定比其他数多。

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int target = 0; // 众数
        int count = 0;  // 计数器

        for (const int& num : nums) {
            if (count == 0) {
                // 此时，假设 nums[i] 就是众数
                target = num;
                count = 1;
            } else if (num == target) {
                count ++;
            } else {
                count --;
            }
        }

        return target;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_cases = {
        {3, 2, 3},
        {2, 2, 1, 1, 1, 2, 2},
    };

    for (auto& nums : test_cases) {
        cout << "Input: ";
        printArray(nums);
        cout << "Output: " << solution.majorityElement(nums) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   摩尔投票法：
       初始化候选元素为数组的第一个元素，计数器为 1。
       遍历数组，如果当前元素与候选元素相同，计数器加 1；否则，计数器减 1。
       如果计数器为 0，当前元素成为新的候选元素，计数器重置为 1。
       最终的候选元素即为多数元素。

   时间复杂度：O(n)
       遍历一次数组，时间复杂度为 O(n)。
   空间复杂度：O(1)
       使用了常数级别的额外空间，空间复杂度为 O(1)。
*/
// majorityElement 返回数组中的多数元素
func majorityElement(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}

	// 初始化候选元素和计数器
	majority, count := nums[0], 1

	// 遍历数组
	for i := 1; i < n; i ++ {
		if count == 0 {
			// 如果计数器为 0，当前元素成为新的候选元素
			majority = nums[i]
			count = 1
		} else if nums[i] == majority {
			// 如果当前元素与候选元素相同，计数器加 1
			count ++
		} else {
			// 如果当前元素与候选元素不同，计数器减 1
			count --
		}
	}

	return majority
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected int
	}{
		{
			nums:    []int{3, 2, 3},
			expected: 3,
		},
		{
			nums:    []int{2, 2, 1, 1, 1, 2, 2},
			expected: 2,
		},
	}

	for i, tc := range testCases {
		result := majorityElement(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}