You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
9
9
10
10
You may assume that the array is non-empty and the majority element always exist in the array.
11
11
12
-
Solution: Runtime: O(n) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x:
12
+
Solution:1.Runtime: O(n) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x:
13
13
If the counter is 0, we set the current candidate to x and the counter to 1.
14
14
If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.
15
15
After one pass, the current candidate is the majority element. Runtime complexity = O(n).
16
+
2. Runtime: O(n) — Bit manipulation: We would need 32 iterations, each calculating the number of 1's for the ith bit of all n numbers. Since a majority must exist, therefore, either count of 1's > count of 0's or vice versa (but can never be equal). The majority number’s ith bit must be the one bit that has the greater count.
