Shulou(Shulou.com)06/01 Report--

This article mainly shows you "LeetCode how to find the absolute number in the array", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "LeetCode how to find the absolute number in the array" this article.

Definition: an absolute mode is a number in which the number of a number in a set of numbers is more than 1 Universe 2.

For example, give you a shaping array of length N:

[13,12,53,12,23,343,12,12]

What would you do if you were asked to find out the elements that appear more than Nhand 2 among them (assuming that there must be such elements in an array)? If you are solving violently and the time complexity is O (n ^ 2), then low!

Six algorithms, in parentheses is the average time of each algorithm I tested through the OJ, let's explain them one by one.

Hash table (22ms)

Sorting method (23ms)

Random number method (19ms)

Moore voting method (19ms)

Divide and conquer (26ms)

Bit operation method (25ms)

1. Hash table method

Code:

Int majorityElement (std::vector & nums) {

Std::mapcounter

For (int I = 0; I

< nums.size(); ++i) if(++counter[nums[i]] >

Nums.size () / 2)

Return nums [i]

}

Using a hash table, store the number of times of each value, and add one when you encounter one, until the number of times of this value is greater than nbind 2 (note that there can be only one number, and the number of occurrences is greater than nmax 2).

2. Sorting method

Code:

Int majorityElement (std::vector & nums) {

Nth_element (nums.begin (), nums.begin () + nums.size () / 2magnum. End ())

Return nums [nums.size () / 2]

}

The code is the most concise, only two sentences. It's also easy to understand, using nth_element () in STL. By calling the nth_element (start, start+n, end) method, you can make the element before the nth large value smaller than the element in this position, and the element after this position is larger than the element in this position. But they are not necessarily orderly. Since the number of occurrences of our absolute mode is greater than that of nmax 2, the element with the largest n / 2 after sorting must be this absolute mode.

3. Random number method

Code:

Int majorityElement (std::vector & nums) {

Srand ((unsigned) time (NULL))

/ / get the seed of random number

While (1) {

Int counters = 0

Int index = rand ()% nums.size ()

For (int I = 0; I

< nums.size(); ++i) { if (nums[index] == nums[i]){ ++counters; } if (counters >

Nums.size () / 2) {

Return nums [index]

}

}

}

}

Principle: randomly find a number and then calculate the number of occurrences of this number in this array, and return this number if it is greater than nUnix 2.

At first I thought the algorithm would be very slow because the worst-case scenario was O (n ^ 2), but unexpectedly, it was almost the fastest algorithm (19ms) among the average results of 44 tests, similar to the Moore voting method.

IV. Moore Voting method (dynamic programming)

Code:

Int majorityElement (std::vector & nums) {

Int major = 0, counters = 0

For (int I = 0; I

< nums.size(); ++i) { if(!counters){ major = nums[i]; counters = 1; } else counters += (major == nums[i]) ? 1:-1; } return major;//因为假设一定存在绝对众数，所以可以直接返回 } 原理：定位major为数组中的某个数，遇到同样的数加一，不同的数减一，若为0则去掉这个定位，重新定位另外一个数，最后要么返回绝对众数，要么不存在绝对众数，由于题目中已经假设一定存在绝对众数，所以不存在的情况不需要考虑。 五、分治法 代码： int majorityElement(std::vector &nums){ return majority(nums, 0, nums.size()-1); } int majority(std::vector &nums,int left,int right){ if (left == right) { return nums[left]; } int mid = left + ((right - left) >

> 1)

Int lm = majority (nums, left, mid)

Int rm = majority (nums, mid + 1, right)

If (lm = = rm) {

Return rm

}

Return std::count (nums.begin () + left, nums.begin () + right + 1, lm) > std::count (nums.begin () + left, nums.begin () + right + 1, rm)? Lm: rm

}

Principle: through the idea of divide and conquer, calculate the number that appears the most on the left and right sides, and then compare it to see which one appears more times and returns more times. It is worth noting that the count method in STL is used here, which uses a pair of iterators and a value as parameters to return the number of times the value appears.

PS: the bit operator is used when calculating mid in the middle. > > 1 is actually divided by 2. Cannot directly (left+right) / 2 because left+right may overflow.

6. Bit operation method

Code:

Int majorityElement (vector& nums) {

Int major = 0

For (int I = 0BI mask = 1; I < 32; + + iBI mask

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.