One, foreword

Hello everyone, this is the first article in a series of articles titled “Offer of the Day”.

In this series of articles, I will review the data structure and algorithm basis by brushing questions for practice, and I will also share my brushing process in the form of blog. If you happen to want to brush up on algorithms, encourage each other to learn. My algorithm foundation is weak, and I hope to make up for this loophole in the next two or three months. The language used for this brush is Java, and it is expected that Python will be used for the second brush.

  • Brush topic platform for Leetcode’s sword Offer topic

  • Code cloud warehouse address: gitee.com/xiaoleiStud…

Second, the subject

Find duplicate numbers in the array

All numbers in an array of length N, nums, are in the range 0 to n-1. Some numbers in the array are repeated, but we don’t know how many are repeated, or how many times each number is repeated. Please find any duplicate number in the array.

Example 1:

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

Limitations:

2<= n <= 100000

Third, the idea of solving the problem

3.1 Idea 1: Comparison after sorting

Find any number that is repeated in an array.

So a simple way to think about it is to sort the array, and then walk through the array, comparing pairs, finding duplicate elements.

3.1.1 Code implementation

Java code implementation:

private static int solove1(int[] nums) { quickSort(nums,0,nums.length-1); int repeat = -1; for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) { repeat=nums[i]; break; } } return repeat; } public static void quickSort(int[] arr, int L, int L) {public static void quickSort(int[] arr, int L int R) { int i = L; int j = R; // pivot = arr[(L + R) / 2]; While (pivot > arr[I]) I ++; pivot (pivot > arr[I]) I ++; pivot (pivot > arr[I]) I ++; While (pivot < arr[j]) j--; If (I <= j) {int temp = arr[I]; if (I <= j) {int temp = arr[I]; arr[i] = arr[j]; arr[j] = temp; i++; j--; }} // The above while ensures that the left side of the fulcrum is smaller than the fulcrum, and the right side of the fulcrum is larger than the fulcrum. If (L < j) quickSort(arr, L, j); If (I < R) quickSort(arr, I, R); }Copy the code
3.1.2 Code execution results

The effect of this approach is as follows

3.1.3 Complexity Analysis

This time, quicksort is used to sort first without applying for extra space. The time complexity of quicksort is O(nlogn) and space complexity is O(1).

3.2 Idea 2: hash table implementation

Hash table to solve this problem. Scan each item of the array from beginning to end, use O(1) to determine if the item is in the hash table, and if it is not in the hash table, add it to the hash table; If the number already exists in the hash table, a duplicate number is found and returned.

The time complexity of this algorithm is O(n), but it improves the time efficiency at the expense of a hash table of size O(n).

3.2.1 Code Implementation

Java version:

// Select * from (); Since we only need to find any duplicate number in the array, we can use the set to deal with // time complexity instead: O (n) private static int solove2(int[] nums) {Set<Integer> Set = new HashSet<Integer>(); int repeat = -1; for (int num : nums) { if (! set.add(num)) { repeat = num; break; } } return repeat; }Copy the code
3.2.2 Execution Effect

The effect of this approach is as follows, you can see that the memory consumption increases slightly.

3.3 Idea 3: Switch in place

So this is using the conditions that they give us.

Note that all the numbers in the array are in the range 0 to n-1. If there are no duplicate numbers in the array, the number I will appear at the index I when the array is sorted. Of course there are duplicate numbers in the array, some places may have multiple numbers, and some places may have no numbers.

The breakthrough is that we can iterate over the x element in the array and place it at the index x in the array. When we encounter the number x for the second time, the element with the index X will appear == x, i.e. the current x is a duplicate element.

3.3.1 Algorithm flow

Iterate over numS and set the initial index value to I =0.

  • 1, if nums[I]! = I, indicating that this number is not in our target position, enter to observe it

  • Nums [I] = nums[I]; nums[I] = nums[I]; nums[I] = nums[I]

  • 3, otherwise: swap the value of the element whose index is I and nums[I], and swap the number to the corresponding index position.

  • 4. If none is found after traversal, return -1

If the first value at index 0 is 0, nums[0] =0, and then the second value is 0,

Nums [0] = 0; nums[0] == 0;

3.3.2 Code implementation

Java version:

Private static int solove3(int[] nums) {int temp; for(int i=0; i<nums.length; i++){ while (nums[i]! =i){ if(nums[i]==nums[nums[i]]){ return nums[i]; } temp=nums[i]; nums[i]=nums[temp]; nums[temp]=temp; } } return -1; }Copy the code
3.3.3 Execution Effect

Can only say in place replacement algorithm is really strong! On the other hand, it also tells us to make more use of the conditions in the problem.

Four, summary

This question examines the understanding and programming ability of one-dimensional array. One-dimensional arrays occupy contiguous space in memory, so we can locate the corresponding elements by subscript.

The three typical solutions are summarized here. The journey of Offer brushing will continue in the future. Welcome to exchange and study together.