Preface:
When I used to do math problems, the teacher said: You learn a variety of ways to solve problems. If you come across similar and different problems, you can learn them and improve your ability to solve them. If you write a variety of solutions, you will impress the interviewer.
The following question, which we will implement in a variety of ways, is a common question in the interview.
Given an array of size N, find most of the elements. Most elements are elements that occur more than n over 2 times in the array. Example: int a[3] = {1, 2, 2}, most elements are 2.
You can assume that the array is non-empty and that there will always be a majority of elements in a given array.
Solution 1: hash table
Animation demo:
The code is as follows:
Hash table method: iterating, counting and finding modes, not counting first and then iterating again to find the maximum value.
Time complexity: O(n); Space complexity: O(n)
Solution two: sort
The code is as follows:
After sorting the array, you can directly determine the mode by subscript, this method is simple.
Time complexity: O(nlogn); Space complexity: O(nlogn)
Solution three: divide and conquer
Animation demo:
The code is as follows:
Divide the array, then find the mode on the left and the mode on the right, and compare the found mode to 1/2 of the length of the array.
Time complexity: O(nlogn); Space complexity: O(nlogn)
Solution 4: Boyer-Moore algorithm
Thought: We call the mode +1 and the other numbers -1, and when we add them all up, the sum is obviously greater than 0. From the result itself, we can see that there are more modes than other numbers.
The code is as follows:
Iterate over all the elements in nums. For each element x, before judging x, if count is 0, assign the value of x to more. Then we judge x:
If x is equal to more, the counter count is incremented by 1; If x and more differ, the counter count is reduced by 1.
Time complexity: O(n); Space complexity: O(1)
omg
In the interview process, choose the algorithm you are familiar with, the time and space complexity of the optimal solution, usually train a variety of methods to understand, improve the ability of the algorithm.
Wechat search [Chenmeng Siyu] focus on this different programmer. Author introduction: CSDN top40, original article 1000+, senior /Golang/C++ development, now working in a well-known Internet factory. This account shares backstage development technology, including algorithm and data structure, written test/interview, network programming, database theory, operating system, IT essays