细语呢喃

0%

leetcode 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

1.排序，复杂度O(nlogn)

2.hash ，时间复杂度O(n)，空间复杂度O(n)

1. 摩尔投票(Boyer–Moore majority vote algorithm)，时间复杂度O(n)，空间复杂度O(1)

1. Eliminate all elements except one. Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate: If the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate.
2. Determine if the remaining element is a valid majority element.

1. 维护一个候选数candidate和计数器counter。遍历数组中所有的元素， 设当前的元素为x，若 counter = 0,则 candidate = x, counter = 1; 否则， 根据candidate 与x是否相等来更新counter（相等+1，不等-1）
2. 在遍历一次，判断候选数是否为合法的主元素。

C

Python

leetcode 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

• 若x==a 则cnt_a++
• 若x==b则cnt_b ++
• 若cnt_a ==0 则 a = x, cnt_a =1
• 若cnt_b ==0 则 b = x, cnt_b =1
• 否则 cnt_a-- , cnt_b--

Python