preface

The previous series of articles have shared the basic knowledge of data structure and algorithm, and then share some ideas and implementation of algorithm problems. Interested developers are welcome to read.

Problem description

I have an array, and I want to find any duplicate element in the array. Its rules are as follows:

  1. Given an array of length N, the values of each element in the array range from 0 to N-1
  2. Some numbers in the array are repeated, but we don’t know which ones are repeated or how many times
  3. Find any repeated number in the array

Implementation approach

There are three ways to realize this problem:

  • Sorting method implementation
  • Hash table auxiliary implementation
  • Dynamic sorting method implementation

Next, let’s take a look at each of the three implementations.

Sorting method implementation

The sorting method is divided into two steps:

  1. First sort the array with quicksort
  2. Iterate over the sorted array. If two adjacent elements are equal, the array contains duplicate numbers, and return them.

Let’s test this idea with an example. Declare an array: [8, 1, 2, 3, 4, 3, 3, 4, 5]

  1. Use quicksort to sort the above array, the sorted array is:[1, 2, 3, 3, 3, 4, 4, 5, 8]

  2. Iterate over the number group to determine whether the element at position I is equal to the element at position I +1.
    1. When I = 0, the element at I is 1, the element at I +1 is 2,1! = = 2, continue the next iteration
    2. When I = 1, the element at I is 2, the element at I +1 is 3,2! = = 3, continue the next iteration
    3. When I = 2, the element at I is 3, the element at I +1 is 3,3 = = = 3, there are duplicate numbers in the array, store the element at position I, exit the loop.
  3. Returns the duplicate number found

Time complexity analysis: the time complexity of calling quicksort is O(nlog(n)). After sorting the array, we only need to traverse the number group to find the adjacent one and exit, so the total time complexity is O(nlog(n)).

Space complexity analysis: Because no new space is declared, the space complexity is O(1).

We can solve this problem by using the sorting method, but it needs to sort the array, and the time complexity is high.

Hash table auxiliary implementation

We can declare an additional hash table, and then iterate through the array to see if the elements in the array already exist in the hash table. If they don’t, we put them in the hash table. If they don’t, we return them. Its implementation idea is as follows:

  1. Declare an empty hash table
  2. Iterate through the array, adding the currently iterated element to the hash table if it does not exist, returning the element otherwise

Let’s test this idea with an example. Declare an array: [8, 1, 2, 3, 4, 3, 3, 4, 5]

  1. Declare a hash table:const hashMap = new HashMap()

  2. Iterates through the array to see if the elements in the array are in the hash table.
    1. When I = 0, the element at position I is 8, it’s not in the hash table, put it in the hash table.
    2. When I = 1, the element at position I is 1, it’s not in the hash table, put it in the hash table.
    3. When I = 2, the element at position I is 2, it’s not in the hash table, put it in the hash table.
    4. When I = 3, the element at position I is 3, it’s not in the hash table, put it in the hash table.
    5. When I = 4, the element at position I is 4, it’s not in the hash table, put it in the hash table.
    6. When I = 5, the element at position I is 3, and in the hash table, the element at position I is stored, terminating the loop.
  3. Returns the duplicate number found

Time complexity analysis: The time complexity of O(1) can be used to determine whether the hash table contains the currently traversed elements when traversing the number group. After traversing all elements, n O(1) are needed, so the total time complexity is O(n).

Space complexity analysis: Since an additional hash table is required to store data, in the worst case all elements of the array will be put into the hash table, so the total space complexity is O(n).

When we use hash table aid, we reduce the time complexity, but at the cost of using O(n) space to store the hash table, we trade space for time.

Dynamic sorting method implementation

The values of the elements in the array range from 0 to n-1, and the following conclusions can be drawn:

  • If there are no duplicate elements in the array, the value of the ith element must be the current index (I).
  • If there are duplicate elements in the array, there may be multiple digits in some places and no digits in others

Based on the above conclusions, we can draw the following implementation ideas:

  1. Go through the array from beginning to end, storing the element in position I, denoted by m
  2. If the value of m is equal to the current subscript (I), the traversal continues.
    • Otherwise, it checks whether the value of m is equal to the value of the array subscript m.
    • Return it if equal represents a repeat.
    • If not, swap the element at position I and the element at position M, updating the value of m
    • Continue to determine whether the value of m is equal to the element at index m in the array.

Let’s test this idea with an example. Declare an array: [8, 1, 2, 3, 4, 3, 3, 4, 5]

  • Go through the array from beginning to end, storing the element in position I, denoted by m.
    • When the subscript is 0, m is equal to 8.
  • At this point, the value of m is 8,8 != 0, the element at position 8 is 5,8 != 5, the exchangearray[0]andarray[8]To update the value of m. The swapped array is:[5, 1, 2, 3, 4, 3, 3, 4, 8]
  • At this point, the value of m is 5,5 != 0, the element at position 5 is 3,3 != 5, the exchangearray[0]andarray[5]To update the value of m. The swapped array is:[3, 1, 2, 3, 4, 5, 3, 4, 8]
  • At this point, the value of m is 3,3! = 0, the element at position 3 is 3,3 = = = 3, the element repeats, and returns m.
  • Problem solved. Repeat number 3.

Time complexity analysis: The location of each number can be found only by swapping it twice at most, so the total time complexity is O(n).

Space complexity analysis: All operations are performed in the original array, no extra space is used, so the space complexity is O(1).

With dynamic sorting, we just change the order of the elements in the array, no extra space is used, so the space complexity is reduced, while the time complexity remains O(n). Therefore, this solution is relatively optimal compared with the first two.

The implementation code

Next, let’s see how to implement this, using TypeScript, and let’s see how to design this class. Not all arrays can be solved using the above method. So when we design the class, we need to determine whether the parameters passed by the caller satisfy the problem.

  • Create a new ts file named:ArrayRepeatedNumber.ts
  • createArrayRepeatedNumberClass that declares auxiliary variables and constructors that need to be used within the class. In the constructor, we verify the arguments passed by the caller.
export class ArrayRepeatedNumber {
    private sort: Sort<number>;
    private readonly isTrue: boolean;
    constructor(private array: number[]) {
        this.isTrue = true;
        // Check whether the parameter meets the rule
        if (array == null || array.length <= 0) {
            this.isTrue = false;
            console.log("The array cannot be empty.");
        }
        for (let i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > array.length - 1) {
                this.isTrue = false;
                console.log("Array elements range from 0 to n-1"); }}this.sort = newSort(array); }}Copy the code

Next, let’s look at the code for each of the three implementations.

  • Use the sorting method to solve
getRepeatedToSort(): number | void {
        if (this.isTrue) {
            // Sort the array
            const sortArray = this.sort.quickSort();
            // Duplicate numbers
            let val = -1;
            for (let i = 0; i < sortArray.length; i++) {
                // If two adjacent numbers are equal, there are duplicate numbers in the array
                if (sortArray[i] == sortArray[i + 1]) {
                    val = sortArray[i];
                    break; }}returnval; }}Copy the code
  • Use a hash table
getRepeatedToHashMap(): number | void {
        if (this.isTrue) {
            const hashMap = new HashMap();
            let val = -1;
            for (let i = 0; i < this.array.length; i++) {
                // Return the current element if it exists in the hash table
                if (hashMap.get(this.array[i]) ! =null) {
                    val = this.array[i];
                    break;
                }
                // It does not exist, add it to the hash table
                hashMap.put(this.array[i], 0);
            }
            returnval; }}Copy the code
  • Use dynamic sorting
getRepeated(): number | void {
        if (this.isTrue) {
            for (let i = 0; i < this.array.length; i++) {
                // Store the element at position I
                let m = this.array[i];
                // Check whether the value of m is the same as the current subscript, then continue the next loop
                while(m ! == i) {// Check whether the value of m is equal to the element at position M
                    if (m === this.array[m]) {
                        // If equal, duplicate, return this element
                        return m;
                    }
                    // Swap the element at position I and the element at position m
                    [this.array[i], this.array[m]] = [this.array[m], this.array[i]];
                    // change the value of m
                    m = this.array[i]; }}/ / was not found
            return -1; }}Copy the code

The code address

For the complete code, go to ArrayRepeatedNumber.ts

Write test code

Let’s use the example above to verify that the above code executes correctly.

const arrayRepeatedNumber = new ArrayRepeatedNumber([8.1.2.3.4.3.3.4.5]);
const result = arrayRepeatedNumber.getRepeatedToSort();
if(result ! = = -1&& result ! =null) {
    console.log("Array Repeated Number to Sort: " + result);
}
Copy the code

const arrayRepeatedNumber = new ArrayRepeatedNumber([8, 1, 2, 3, 4, 3, 3, 4, 5]); const result = arrayRepeatedNumber.getRepeatedToSort(); if (result ! == -1 && result ! = null) { console.log("Array Repeated Number to HashMap: " + result); }Copy the code

const arrayRepeatedNumber = new ArrayRepeatedNumber([8, 1, 2, 3, 4, 3, 3, 4, 5]); const result = arrayRepeatedNumber.getRepeated(); if (result ! == -1 && result ! = null) { console.log("Array Repeated Number: " + result); }Copy the code

Write in the last

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌