Interview question 17.10. Key elements
Moore voting: remove/cancel two different elements in sequence so that the number of elements left may be greater than half the number of all elements in the array.
So this might be something like 1212333, where the sequence cancels out 333, and the number of 3’s is obviously not as good as the length of the sequence. The offset is guaranteed to be no more than half the length of the sequence (which I think is the mathematical principle Moore used to vote on).
Summary: Moore voting ensures that the cancelled element is never the primary element, and that the number of elements left may account for more than half of the array.
So with that thought in mind, it’s easy to do this problem, and you can set a variable n to hold the element that will probably have the largest number of elements in the array. Sum is used to store the current amount of the element.
- The first step is to iterate through the array from beginning to end
- Determine if sum is 0; If it is 0, then the current element is treated as the one with the largest possible number of elements in the array, n=sum[I]; If not, keep n.
- If n is equal to the current element, sum-1 means that the number of candidate element n is cancelled once. If n is equal, add one.
The n that comes out here is the one that cancels out the rest of the elements after the Moore vote, and the sum is the one that cancels out the rest of the elements, so we have to use a loop again to count all the n occurrences.
Finally, the statistical quantity sum is compared with nums.length/2 to determine whether it is the main element.
The code is as follows:
var majorityElement = function(nums) { let n=-1 ; let sum =0; for(let i=0; i<nums.length; i++){ n = sum==0? nums[i]:n sum = n==nums[i]? sum+1:sum-1 } sum=0 for(let i =0; i<nums.length; i++){ sum= n==nums[i]? sum+1:sum } return sum>nums.length/2? n:-1 };Copy the code