Leetcode – Interview 17.10- Key elements

[Blog link]

The path to learning at 🐔

The nuggets home page

[Topic Description

Elements that make up more than half of an array are called primary elements. Given an array of integers, find the major elements. If not, return -1. Design a solution whose time complexity is O(N) and space complexity is O(1). Example 1: Input: [1,2,5,9,5,9,5,5] Output: 5 Example 2: Input: [3,2] Output: -1 Example 3: Input: [2,2,1,1, 2,2] Output: 2 Related Topics Array count 👍 100 👎 0Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Boyer-Moore voting algorithm

  • Violence law
  • Each element is stored in a map, and the elements that make up more than half of the array are identified by value
  • Time complexity O(n) Space complexity O(n)
  • I’m not going to write this method because it’s too easy
  • Boyer-moore voting algorithm that’s the first I’ve heard of it
  • The whole idea is to randomly identify a candidate element
  • The count count+1 is used whenever an element is the same as the current element and count-1 is used whenever an element is different
  • When count=0, iterate over the next element, changing the candidate element to the next element
  • Repeat the process
  • Prove the principle, because as long as the element definition is more than half the number of elements in the array
  • So this must cancel out the rest of the elements
  • The remaining elements may be the primary elements
  • The array needs to be scanned again to see if the number of major elements exceeds half of the array
public int majorityElement(int[] nums) {
            int count = 1, master = nums[0], n = nums.length;
            if (n == 1) {
                return master;
            }
            for (int i = 1; i < n; i++) {
                if (count == 0) {
                    master = nums[i];
                }
                if (nums[i] == master) {
                    count++;
                } else {
                    count--;
                }
            }
            count = 0;
            for (int num : nums
            ) {
                if(num == master) { count++; }}// Ensure that the odd number of elements are half the length
            return count >= (n + 1) / 2 ? master : -1;
        }
Copy the code


Time complexity O ( n ) Spatial complexity O ( 1 ) Time complexity O(n) Space complexity O(1)