I have nothing important to do recently, so I have time to look at data structure and write about it, so as to activate my mental thinking.

In computer science, data structures are the ways in which data is stored and organized in a computer. Data structure and algorithm are more abstract, learning or need a certain amount of perseverance. Broadly speaking, data structure refers to the storage structure of a group of data, and algorithm is a group of methods to manipulate data. Algorithms and data structures complement each other. Data structures serve algorithms, which operate on specific data structures.

Introduction to LeetCode Data structures

217. There are duplicate elements

Some of the more unusual test cases:

  • [1, 2, 3, 1)
  • [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
  • [1, 2, 3, 4]
  • [0]
  • [7, 3, 2, 1, 2]
  • [1, 5, -2, -4, 0]
  • [2, 14, 18, 22, 22]

At present, individual thoughts can be divided into three different realization directions:

  • Direction one: Not using the convenience apis provided by arrays
    • In addition to the basic operations (push, POP, unshift, shift, slice, splice)
  • Direction two: You can use all the apis provided by arrays
  • Direction 3: Other skills

Note: The code that appears below can be overwritten using for

Direction of a

1. Double cycle method

1.1 the violence

function containsDuplicate(nums: number[]) :boolean {
    let i = 0
    let j = 0
    while (i < nums.length) { // n
        const item = nums[i]
        while (j < nums.length) { // n
            if (item === nums[j]) {return true}
            j++
        }
        i++
    }
    return false
};
Copy the code

Time complexity: O(n^2) Problem: Self vs. self will be true result: not applicable

1.2 optimization

function containsDuplicate(nums: number[]) :boolean {
    let i = 0
    let j = i + 1
    while (i < nums.length) { // n
        const item = nums[i]
        while (j < nums.length) { // n - 1
            if (item === nums[j]) { return true }
            j++
        }
        i++
        j = i + 1
    }
    return false
};
Copy the code

Time complexity: On(n * (n-1)) => O(n^2) Problem: Because it is sequential, it takes too long to compare duplicate elements at the end of the loop

2. Double pointer

2.1 Space Usage

function containsDuplicate(nums: number[]) :boolean {
    const arr = []

    const findNum = (num: number) :boolean= > {
        let kl = 0
        let kr = arr.length - 1
        while (kl <= kr) {
            if (num === arr[kl] || num === arr[kr]) { return true }
            kl++
            kr--
        }
        return false
    }

    let i = 0
    let j = nums.length - 1

    while (i <= j) { // n / 2 
        const l = nums[i]
        const r = nums[j]
        if (i === j && findNum(l)) { return true } // n / 2+1
        if (l === r) { return true }
        if (findNum(l)) { return true } // n / 2 + 1
        if (findNum(r)) { return true } // n / 2 + 1
        arr.push(l)
        arr.push(r)
        i++
        j--
    }
    return false
};
Copy the code

Time complexity: O(3m * n) => O(mn) Problem: Extra space is needed to record the traversed value, and it needs to be traversed again from the history. Boundary condition results in multiple cases need to be processed: Can be implemented, but the implementation is logically optimized and can be implemented without additional space

2.2 Optimization, no use of space

function containsDuplicate(nums: number[]) :boolean {
   let i = 0
   let j = nums.length - 1

   while (i <= j) { // n
       const l = nums[i]
       const r = nums[j]
       if(l === r && i ! == j)return true
       let ci = i + 1
       let cj = j - 1
       while (ci <= cj) { // n
           if (l === nums[ci] || l === nums[cj]) return true
           if (r === nums[ci] || r === nums[cj]) return true
           ci++
           cj--
       }
       i++
       j--
   }
   return false
};
Copy the code

The boundary condition greatly reduces the time complexity: O(n * n) => O(n^2) Problem: Although no extra space is occupied and the inner loop also uses double Pointers, it does not change its complexity. Result: It can be implemented without changing its complexity

Direction of the second

1. The use of indexOf

function containsDuplicate(nums: number[]) :boolean {
    for (let i = 0; i < nums.length; i++) { // n
        if (nums.indexOf(nums[i], i + 1)! = = -1) return true // n
    }
    return false
};
Copy the code

Time complexity: O(n * n) => O(n^2) Problem: Using the indexOf API implementation, it looks like O(1) but is still O(n) internal result: achievable

2. The use of the sort

function containsDuplicate(nums: number[]) :boolean {
    if(! nums || ! nums.length)return false

    nums = nums.sort()
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === nums[i + 1]) return true
    }
    return false
};
Copy the code

Time complexity: O(n + n) => O(n) Problem: Elements of a single type are feasible. If complex types occur, more cases need to be considered. Result: Yes

Direction of # 3

1. Use the object key

function containsDuplicate(nums: number[]) :boolean {
  if(! nums || ! nums.length)return false

  const obj: { [key: string] :number } = {}
  for (let i = 0; i < nums.length; i++) {
    if (obj[nums[i]]) { return true }
    if(! obj[nums[i]]) { obj[nums[i]] =1}}return false
};
Copy the code

Features: Using the non-repeatable key of the object, if the existing key is encountered, it can be confirmed that there are duplicate elements: O(n) Problem: Using the type feature, but not the result of algorithm implementation: achievable

2. Use the Set new data type

function containsDuplicate(nums: number[]) :boolean {
  if(! nums || ! nums.length)return false

  const nNums = new Set(nums)
  return nums.length > nNums.size
};
Copy the code

Features: Using the Set natural de-weight feature, through the array length comparison can be directly concluded time complexity: O(1) problem: belongs to the use of type characteristics, not algorithm implementation results: can be achieved

3. Make use of Map new data types

function containsDuplicate(nums: number[]) :boolean {
  if(! nums || ! nums.length)return false

  const nNums = new Map(a)for (let i = 0; i < nums.length; i++) {
    if (nNums.has(nums[i])) { return true }
    else { nNums.set(nums[i], 1)}}return false
};
Copy the code

Time complexity: O(n) Problem: Using type feature, not algorithm implementation result: achievable