This is the second day of my participation in the More text Challenge. For more details, see more text Challenge

preface

At the request of “Wang Yu”, I started to brush the LeetCode Top selected interview questions yesterday to prepare for autumn recruitment.

Topic describes

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

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

Example 1:

Input: [1,2,3,1] output: true

Example 2:

Input: [1,2,3,4] output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2] output: true

Play ~

解 决 解 决 : Array to Set to deduplicate. The size of the Set is equal to the length of the array. It’s not equal. It has repeating elements

var containsDuplicate = function(nums) {
    return new Set(nums).size ! == nums.length };Copy the code

Ha ha ha, some people say you this is what ah, I also can, don’t hurry, first heat a body, come, force buckle brush brush train of thought although late but arrive ~

The sorting

After sorting the numbers from smallest to largest. The duplicate elements of an array must appear in adjacent positions, so we can scan the sorted array and check whether the adjacent elements are equal each time. If they are equal, then there are duplicate elements.

var containsDuplicate = function(nums) {
  // Arrange the array in ascending order
  nums.sort((a, b) = > a - b);
  // The length of the array
  const n = nums.length;
  // Loop through the array because I +1 is required, so n-1 is not available here.
  for (let i = 0; i < n - 1; i++) {
    if (nums[i] === nums[i + 1]) {
      return true; }}return false;
};
// Time complexity: O(NlogN), where N is the length of the array. You need to sort the array.
// Space complexity: O(logN), where N is the length of the array. Note that we should consider the depth of the recursive call stack here
Copy the code

The hash map

For each element in the array, we insert it into the hash table. If we insert an element that already exists in the hash table, then there are duplicate elements.

var containsDuplicate = function(nums) {
 const map = new  Map(a)for(let i of nums) {
     if(map.has(i)){
         return true
     } else {
         map.set(i,1)}}return false
};
// Time complexity: O(N), where N is the length of the array.
// Space complexity: O(N), where N is the length of the array.
Copy the code

Meat today

For today’s meal, I chose LeetCode136, which only appears once

Given an array of non-empty integers, each element appears twice except for one that appears only once. Find the element that appears only once.

var singleNumber = function(nums) {
    // Method 1 compares before and after sorting
    nums.sort((a,b) = > a - b);
    for(let i = 0; i < nums.length; i++){
        if(nums[i-1]! == nums[i] && nums[i] ! == nums[i+1]) 
        return nums[i];
    }
    
    // Method 2 uses map
    let map = new Map(a); nums.forEach(item= >{
        map.set(item, map.has(item) ? map.get(item) + 1 : 1);
    })
    for(let [key, val] of map.entries()){
        if(val === 1) return key;
    }

    // Method 3 xor operation
    return nums.reduce((pre,cur) = > pre ^ cur);
};
Copy the code

Npy: I can’t understand the xor of method 3!!

Me: Ok, ok, let me explain it to you, and then give you a simple idea

First of all, for xOR operation, here is a summary of knowledge:

Xor any number with itself, and the result is not zero, which is a star a=0a star a=0. If you do the xOR operation on any number with not not, you’re going to get itself, which is a⊕0=⊕a⊕0=⊕. Exclusive or operation, meet the commutative law and associative law, namely the radius b radius a = b radius radius radius a = b = b (a radius a) radius 0 = ba radius radius b a = b radius radius radius a = b = b (a radius a) radius 0 = b.

var singleNumber = function(nums) {
    let ans = 0;
    for(let i = 0; i < nums.length; i++){
        ans ^= nums[i];
    }
    return ans;
};
Copy the code

conclusion

Swipe the question and punch in the 8th day, choose the force button 217, 136, learn an element in the array or repeat elements, together refueling ~

❤️ Thank you all

If you think this content is very helpful to you: like support, let more people can also see this content (collection does not like, is playing rogue – -) follow the public number to NPY front secret, we learn together progress. If you like it, you can also read other articles (thanks to friends for their encouragement and support 🌹🌹🌹)

Start the LeetCode tour

Double pointer to LeetCode

Leet27, remove element

Classic sorting algorithms that front-end engineers must learn

LeetCode20, bracket match

LeetCode7, integer inversion

LeetCode344, inverts the string