? ? ? ? leetcode原題鏈接：多數元素

題目描述

? ? ? ? 給定一個大小為?n?的數組?nums?，返回其中的多數元素。多數元素是指在數組中出現次數?大于?? n/2 ??的元素。你可以假設數組是非空的，并且給定的數組總是存在多數元素。

示例?1：

輸入：nums = [3,2,3]
輸出：3

示例?2：

輸入：nums = [2,2,1,1,1,2,2]
輸出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

進階：嘗試設計時間復雜度為 O(n)、空間復雜度為 O(1) 的算法解決此問題。

解題方法：用兩個變量分別保存結果result和當前正在掃描的某一個數字的總數count。

1. 遍歷數組，當遇到跟結果變量result相同的數字時加一，遇到跟result不同的數字時減一。

2. 當count為0的時候，重新更新result的值。

C++代碼

#include <iostream>
#include <vector>class Solution {
public:int majorityElement(std::vector<int>& nums) {int n = nums.size();if (n == 0) {return -1;}int result = 0;int count = 0; //記錄當前未被消除的數字for (auto num : nums) {if (count == 0) { // 每次優勢票清0后，重新選舉新的元素result = num;count++;} else if (num == result) { //count不等于0，且當前掃描的元素是優勢票,則繼續加強優勢票的計數count++;} else { // count不等于0，且當前掃描的元素非優勢票,則削弱優勢票的計數count--;}}return result;}
};