【LeetCode】Majority Element(求主元素)

说明

这道题出现在了王道的《2019数据结构考研复习指导》的18页,LeetCode中也有这道题。题目大意是:给定一个长度为n的数组,我们定义"主元素"为数组中出现次数超过⌊n/2⌋的元素。

Description

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

解析

设数组为nums, 主元素为data,主元素出现的次数为count;

  1. 假设第一个元素可能成为主元素,则data = nums[0],count=1
  2. i = i + 1, 比较nums[i]是否等于当前的主元素data,如果相等则说明data出现的次数又多了一次,count = count + 1;如果不相等,则让count = count - 1
  3. 如果count为0, 让data = nums[i](假设为主元素)
  4. 重复2、3步,直到遍历完所有的元素。
  5. 如果count > 0,遍历所有的元素,统计出值等于data的元素的个数c,如果元素个数c大于 > n/2,则说明data是该数组的主元素。

此算法的基本思想就是如果某个元素是数组nums的主元素,则它出现的次数一定大于数组元素的一半,且一定是最后一个重置data的元素。
时间复杂度: O(n),空间复杂度: O(1)

C++实现

#include <iostream> #include <vector> using namespace std; int majorityElement(vector<int> &nums); int main() { int n; vector<int> nums; cin >> n; // 第一行输入n(元素的总数) while (n--) // 依次读取n个数字 { int t; cin >> t; nums.push_back(t); } int element = majorityElement(nums); cout << element; return 0; } int majorityElement(vector<int> &nums) { if (nums.empty()) return -1; if (nums.size() == 1) return nums[0]; int count = 1; int data = nums[0]; for (int i = 1; i < nums.size(); ++i) { if (data == nums[i]) count++; else count--; if (count == 0) { data = nums[i]; count = 1; } } int c = 0; if (count > 0) { for (int i = 0; i < nums.size(); ++i) { if (data == nums[i]) c++; } } if (c > nums.size() / 2) return data; else return -1; }

本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明: 作者staneyffer,首发于我的博客,原文链接: https://chengfy.com/post/7


载入评论中....