Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/169.html
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.
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
-109 <= nums[i] <= 109
Follow-up: Could you solve the problem in linear time and in O(1)
space?
Algorithm
First of all, there is a prerequisite, there must be a number that appears more than half of the number, then if the counter is reduced to 0, it means that the number of numbers that are not candidates currently is the same as the number of candidates, then this candidate It is already very weak, and it may not appear more than half. At this time, choose to replace the current candidate.
Or, after sorting, mid is always the majority.
Code
-
public class Majority_Element { public class Solution { public int majorityElement(int[] nums) { int res = 0, cnt = 0; for (int num : nums) { if (cnt == 0) {res = num; ++cnt;} else if (num == res) ++cnt; else --cnt; } return res; } } class Solution_logN { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } } } ############ class Solution { public int majorityElement(int[] nums) { int cnt = 0, m = 0; for (int v : nums) { if (cnt == 0) { m = v; cnt = 1; } else { cnt += (m == v ? 1 : -1); } } return m; } }
-
// OJ: https://leetcode.com/problems/majority-element/ // Time: O(N) // Space: O(1) class Solution { public: int majorityElement(vector<int>& nums) { int ans = 0, cnt = 0; for (int n : nums) { if (ans == n) ++cnt; else if (cnt > 0) --cnt; else { ans = n; cnt = 1; } } return ans; } };
-
class Solution: def majorityElement(self, nums: List[int]) -> int: cnt = m = 0 for v in nums: if cnt == 0: m, cnt = v, 1 else: cnt += 1 if m == v else -1 return m ############ class Solution(object): def majorityElement(self, num): return sorted(num)[len(num) / 2]
-
func majorityElement(nums []int) int { cnt, m := 0, 0 for _, v := range nums { if cnt == 0 { m, cnt = v, 1 } else { if m == v { cnt++ } else { cnt-- } } } return m }
-
/** * @param {number[]} nums * @return {number} */ var majorityElement = function (nums) { let cnt = 0, m = 0; for (const v of nums) { if (cnt == 0) { m = v; cnt = 1; } else { cnt += m == v ? 1 : -1; } } return m; };
-
public class Solution { public int MajorityElement(int[] nums) { int cnt = 0, m = 0; foreach (int v in nums) { if (cnt == 0) { m = v; cnt = 1; } else { cnt += m == v ? 1 : -1; } } return m; } }
-
impl Solution { pub fn majority_element(nums: Vec<i32>) -> i32 { let mut m = 0; let mut cnt = 0; for &v in nums.iter() { if cnt == 0 { m = v; cnt = 1; } else { cnt += if m == v { 1 } else { -1 }; } } m } }
-
class Solution { /** * @param Integer[] $nums * @return Integer */ function majorityElement($nums) { $major = 0; $count = 0; for ($i = 0; $i < count($nums); $i++) { if ($count == 0) $major = $nums[$i]; if ($major == $nums[$i]) $count++; else $count--; } return $major; } }
-
function majorityElement(nums: number[]): number { let cnt: number = 0; let m: number = 0; for (const x of nums) { if (cnt === 0) { m = x; cnt = 1; } else { cnt += m === x ? 1 : -1; } } return m; }