[アルゴリズム]LeatCode-Majority Element
LeetCode - Majority Element
問題の説明
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
I/O例
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
せいげんじょうけん
Constraints:
n == nums.length
1 <= n <= 5 * 104
-231 <= nums[i] <= 231 - 1
Solution
ソート後、maxCountの要素を順番にナビゲートして検索します.
[方法2]ハッシュマッピングを使用して各要素のカウントを計算する
[方法3]Boyer-Moore Vootingアルゴリズム(ソリューションを参照)
-多くの要素が配列全体の2/n以上を占めます.class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
Reference
この問題について([アルゴリズム]LeatCode-Majority Element), 我々は、より多くの情報をここで見つけました
https://velog.io/@jerry92/알고리즘-LeetCode-Majority-Element
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Constraints:
n == nums.length
1 <= n <= 5 * 104
-231 <= nums[i] <= 231 - 1
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
Reference
この問題について([アルゴリズム]LeatCode-Majority Element), 我々は、より多くの情報をここで見つけました https://velog.io/@jerry92/알고리즘-LeetCode-Majority-Elementテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol