This is the 19th day of my participation in the Genwen Challenge

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

128. Contains -duplicate elements

The label

  • Array
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given an array of integers, determine whether there are duplicate elements.

The function returns true if there is a value that appears in the array at least twice. Return false if each element in the array is different.

Example 1:

Input: [1,2,3,1] output: trueCopy the code

Example 2:

Input: [1,2,3,4] output: falseCopy the code

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2] output: trueCopy the code

The basic idea

Sorting implementation

  1. Sort first so that the array’s repeating elements must appear in adjacent positions
  2. Iterating to determine if adjacent elements are equal, returns true if there are duplicates, false otherwise

Hash table

  1. Each element is stored in the hash table.
  2. When an element is inserted and found to already exist in the hash table, duplicate elements exist.

The downside is that it requires extra space.

Writing implement

  1. Sorting implementation
var containsDuplicate = function(nums) {
    / / first order
    nums.sort((a, b) = > a - b);

    // Iterate over and compare adjacent elements, returning true if there are duplicates, false otherwise
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] === nums[i + 1]) {
            return true; }}return false;
};

let nums = [1.2.3.1]
console.log(containsDuplicate(nums))
Copy the code
  1. A hashMap implementation
var containsDuplicate = function(nums) {
    let map = new Map(a)for (let i = 0; i < nums.length; i++) {
        // When an element exists in a hashMap, there are duplicate elements
        if (map.has(nums[i])) {
            return true
        } else {
            map.set(nums[i])
        }
    }
    return false
};

let nums = [1.2.3.1]
console.log(containsDuplicate(nums))
Copy the code

129. kth-largest element-in-an-array 129. kth-largest element-in-an-array

The label

  • Array
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Finds the KTH largest element in the unsorted array. Note that you need to find the KTH largest element of the sorted array, not the KTH distinct element.

Note: You can assume that k is always valid and that 1 ≤ k ≤ the length of the array.

Example 1:

Input: [3,2,1,5,6,4] and k = 2 output: 5Copy the code

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4 output: 4Copy the code

The basic idea

Quick sort

If you are not familiar with quicksort, take a look at this brief introduction to quicksort

We want the KTH largest element, that is, the KTH largest element in order from smallest to largest, so combining the array let’s see:

  • In the array1 bigThe element is thetaFrom smallest to largest len - 1Element of the subscript (that is, the last one)
  • In the arrayThe first big kThe element is thetaFrom smallest to largest len - k The subscript positionThe elements of the
  • We need toPosition len-k 的The left-hand side is less than that.The right-hand side is bigger than that, thennums[len - k]isThe KTH largest elementThat’s the idea of quickplatoon. (Consider Len-K as the benchmark)

Writing implement

Quick sort

var findKthLargest = function (nums, k) {
  const n = nums.length;

  const quickSort = (left, right) = > {
    if (left < right) {
      let pivot = nums[right];
      let pivotIndex = left;

      for (let i = left; i < right; i++) {
        if (nums[i] < pivot) {
          [nums[i], nums[pivotIndex]] = [nums[pivotIndex], nums[i]]
          pivotIndex++;
        }
      }
      [nums[right], nums[pivotIndex]] = [nums[pivotIndex], nums[right]]

      // When n-k == pivotIndex
      // The left element is smaller than nums[n-k], and the right element is larger than nums[n-k], which is the KTH element
      if (n - k < pivotIndex) {
        // If n-k is less than pivotIndex, continue looking to the left
        quickSort(left, pivotIndex - 1);
      } else {
        // If n-k is greater than pivotIndex, continue to look to the right
        quickSort(pivotIndex + 1, right); }}}; quickSort(0, n - 1);
  return nums[n - k];
};


let nums = [3.2.3.1.2.4.5.5.6], k = 4
console.log(findKthLargest(nums, k))
Copy the code

Sort library function implementation

var findKthLargest = function(nums, k) {
    nums.sort((a, b) = > a - b)
    return nums[nums.length - k]
};

let nums = [3.2.3.1.2.4.5.5.6], k = 4
console.log(findKthLargest(nums, k))
Copy the code

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference