This is the 31st day of my participation in the August More Text Challenge

The number that occurs more than half The Times in an array

Offer 39. A number that occurs more than half the time in the array

Difficulty: Easy

Topic: leetcode-cn.com/problems/sh…

Find a number that occurs more than half the length of the array.

You can assume that the array is non-empty and that a given array always has most elements.

Example 1:

Input: [1, 2, 3, 2, 2, 2, 5, 4, 2] Output: 2Copy the code

Limit: 1 <= Array length <= 50000

Answer key

If a number occurs more than half of the length of the array, it can be found in three key ways:

  • Hash table method: iterate over numS, use Map to count the number of numbers, you can find outstanding numbers, time and space complexity is O(N).
  • Array sort method: sort the array nums, the point in the array must be mode.
  • Moore voting method: the core idea is that the number of votes is positive and negative offset, the time complexity is O(N), the space complexity is O(1).

Method of hash table

/ * * *@param {number[]} nums
 * @return {number}* /
var majorityElement = function(nums) {
	var map = new Map(a);for(let i = 0; i < nums.length; i++){// Store the array elements and occurrences in the map
    if(map[nums[i]] === undefined){
    	map[nums[i]] = 1;   
    }else{ map[nums[i]]++; }}// Traverses all elements in the map whose number exceeds half of the nums length
  for(let item in map){
    if(map[item] >= Math.ceil(nums.length/2)) {returnitem; }}};Copy the code

Method two array sort

var majorityElement = function(nums) {
  let num = nums.sort();
  return num[Math.floor(num.length/2)];// To avoid input of only one number, five is undefined
}
Copy the code

Three moors of voting

The principle is similar to mutually fatal, mode and non mode offset one by one, the final left will be the mode (votes > 0).

var majorityElement = function(nums) {
  let x = 0, votes = 0; // x is the mode number and votes is the sum number
  for(let i = 0; i < nums.length; i++){if(! votes){// If votes is 0, the mode is set to the current subscript value
      x = nums[i];
      votes++;
    }else{ // If the subscript value is mode, add 1; otherwise, subtract 1
      votes += nums[i] === x ? 1 : -1; }}return x;
}
Copy the code

The smallest number of k

Offer 40. Minimum number of k

Difficulty: Easy

Topic: leetcode-cn.com/problems/zu…

Enter the integer array arr to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4.

Example 1:

Input: arr = [3,2,1], k = 2 output: [1,2] or [2,1]Copy the code

Example 2:

Input: arr = [0,1,2,1], k = 1Copy the code

Limitations:

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

Answer key

Method one calls the API directly

/ * * *@param {number[]} arr
 * @param {number} k
 * @return {number[]}* /
var getLeastNumbers = function(arr, k){
  // sort uses quicksort
  return arr.sort((a, b) = > a - b).slice(0, k);
}
Copy the code
  • Time complexity: O(NlogN)
  • Space complexity: O(logN)

Method 2 fast array partition

We just need to find TopK, so we don’t have to sort all of the elements, as opposed to method one, and we don’t have to order all of the k elements, so we optimize quicksort so that it doesn’t sort the entire array.

Steps:

  1. The guard division:
    • Divide the array through a sort. The base number is ARR [I], the left range is [LLL, I − 1i-1I −1], and the right range is [I +1i+1i+1, RRR].
  2. Recurse or return(k+1 is the number before and after k.)
    • If k
    • If k> IK > IK > I, the k+1k+1k+1 smallest number is in the right subarray, recurse to the right subarray
    • If k=ik =ik = I, arr[k] is the smallest number of k+ 1K + 1K +1
var getLeastNumbers = function(arr, k){
  if(k >= arr.length) return arr;
  return quickSort(arr, k, 0, arr.length - 1);
}
function quickSort(arr, k, l, r){
    let i = l, j = r;
    while(i < j){
      while(i < j && arr[j] >= arr[l]) j--;
      while(i < j && arr[i] <= arr[l]) i++;
      [arr[i],arr[j]] = [arr[j],arr[i]];
    }
    [arr[i],arr[l]] = [arr[l],arr[i]];
    if(i > k) return quickSort(arr, k, l, i - 1);
    if(i < k) return quickSort(arr, k, i + 1, r);
    return arr.slice(0, k);
  }
Copy the code
  • Time complexity: O(N)
  • Space complexity: O(logN)

Practice every day! The front end is a new one. I hope I can get a thumbs up