Here is the title: https://leetcode-cn.com/problems/find-majority-element-lcci/

Topic analysis:

Be sure to see the problem clearly. In the problem, please design a solution with time complexity of O(N) and space complexity of O(1).

Train of thought analysis:

This problem is not difficult to understand. Find the element with the most occurrences, and the occurrence of the element needs to be greater than half the length of the whole array.
If two elements appear the same number of times, there is no "main element"
There are many ways to use leetcode, but we need to think about those that meet the complexity of time and space

Method I:

We can directly traverse to find the element with the most occurrences, and the probability of the occurrence of the element, and then see if it is greater than half the length of the array.

nums = [1,2,5,9,5,9,5,5,5]
nums.sort() 
mid = nums[len(nums) // 2]
count = nums.count(mid)
if count > len(nums) // 2:
    print(mid)
else:
    print(-1)

This is an easy to understand method, but the leetcod directly timed out.

Method 2:

After careful study of the topic, it is found that if there are "main elements" in the array, when the array is sorted. The number in the middle must be the "main element".
So we can sort the array, find the number in the middle, count its times, and finally verify whether the number of occurrences is greater than half the length of the array.

 nums.sort()
 mid =nums[len(nums) // 2]
 count = nums.count(mid)
 if count > len(nums) // 2:
     print(mid)
     return mid
 else:
     print(-1)
     return -1

be careful:
The sort() sorting method in Python 3 is known by Baidu as a sort method called timport. The average time complexity is: O(nlogn)
Therefore, the above methods do not meet the requirements of the topic.
But you can use leetcod.

Method 3:

Use a hash table to store the element and the number of times the element has occurred.
Finally, traverse the hash table to see which value is greater than the length of the array, and output the value of the key corresponding to the value.

Full code:

nums = [6,5,5]
hashmap = {}
for i in nums: 
    if i in hashmap: # If the element is in the hash table, the corresponding value is added by 1
        hashmap[i] += 1
        continue
    hashmap[i] = 1 # If the element is not in the hash table, it is added to the hash table
print(hashmap)
for key,value in hashmap.items(): # Traversal hash table
    if value > len(nums) // 2: # determine whether it is greater than half the length of the array
        print(key)
        return key
return -1

This method can be through leetcode.
The time complexity is O(n), but a hash table is opened, and the space complexity does not meet the requirements of the topic.

Method 4:

Using the Moore voting method, we set a count variable. Then traverse the array. Count increases by 1 when the same element appears, and decreases by 1 when different elements appear.
If the value of the last count is > 0, it indicates that there may be a "main element". Not necessarily, because the number of occurrences of the element is not necessarily greater than half the length of the array.

Set up a res to record possible answers.

Several points for attention:

What happens when the voting counter count = 0?

1. Obviously, it was just entering the cycle at the beginning. For example, array [a,a,b]
At the beginning of the loop, the current value res=a is recorded when count = 0 just enters the array

2. In another case, for example, the array [a,b,b] starts with 0. Start traversal.
Encounter a plus 1, encounter b minus 1. At this time, the count is 0
Then record the current value res=b

So we come to the conclusion that when the traversal is not completed, the voting counter count = 0 appears. Then the current may be the answer. Record it in res.

A friend asked: the new res that appears behind will cover the possible answers in front.
There is no need to worry about this at all, because if a new res appears, it means that the count is 0
It must be a new element that appears the most times, which will cause the count to become 0 again.

For example, array [a,a,b,c,c,c]

Obviously, the initial res is recorded as a.
Change of count:
When a is encountered, it becomes 1
When a is encountered, it becomes 2
b becomes 1
When C is encountered, it becomes 0 (record C to res at this time)
c becomes 1
c becomes 2
Finally, the value c with count of 2 and the most occurrences of res records.

So when count = 0. When res is overwritten, it indicates that there are more elements.

When we look for the most frequent element. Finally, you only need to judge whether the number of occurrences of this element is greater than half the length of the array.

Full code:

nums = [2,2,2,3,3,4,4]

if not nums: # If num is null, - 1 will be returned directly
    return -1

res, count = None, 0  # res records possible answers, and count is the voting counter

for num in nums:   # Traversal nums
    if count == 0:  # When count is 0. The possible answer appears
        res = num  # Record possible answers
        count += 1
    else:  
        if num == res:
            count += 1
        else:
            count -= 1
if count == 0:  # After the voting is completed, the count is still 0, indicating that there is no maximum number.
    return -1

identify = 0

for num in nums: # Is there more than half of the number of current records
    if num == res:
        identify += 1
        if identify > len(nums)/2:
            return res
return -1