Topic describes
- Difficulty: Easy
- 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.
- The sample
Input:2.3.1.0.2.5.3] output:2 或 3
Copy the code- Limit: 2 <= n <= 100000
Thought analysis
A brute force algorithm
- Iterate violently through two for loops, comparing the i-th number to the number after I. If so, a duplicate number is found and returned. If not, I ++ is used until the end. (I starts with 0).
- Obviously, this is going to take O(n^2) time, O(1) space. Such time complexity is too high, so we need to find ways to reduce time complexity.
Quicksort + traversal
- I +1 = I +1 = I +1 = I +1 = I +1 = I +1 = I +1 = I +1 = I +1 (I starts with 0).
- The time complexity is reduced by fast sorting, O(nlogn + n) => O(nlogn) (big O notation), space complexity is O(1).
Space for time
- Actually see this topic, I first recall is a deep clone of JavaScript implementation method, we can through the establishment of an empty object (hash table), and then iterate through group, if the object (hash) without the current array elements, then add it into the object, if present, is found a repeat number and return.
- By trading space for time in this way, the time complexity is O(n), and the space complexity is O(n).
- Deep clone implementation
// * Custom function to implement deep clone
var obj1 = {
name: 'moonlightop'.age: 20.sex: 'man'.card: ['kai'.'chong']}var obj2 = {
name: 'hao',}function DeepClone (Origin,Target) {
// Clone Origin to Target (object), return the cloned Target
Target = Target || {};
// Iterates over all key-values, dividing them into reference values and original values
for (var prop in Origin) {
if (Origin.hasOwnProperty(prop)) {
// typeof null -> object
if(Origin[prop] ! = =null && typeof(Origin[prop]) === 'object') {
// array object (typeof)
if (Object.prototype.toString(Origin[prop]) === '[object object]') {
// object
Target[prop] = {};
} else {
// array
Target[prop] = [];
}
DeepClone(Origin[prop],Target[prop]);
} else {
// number string function boolean null undefinedTarget[prop] = Origin[prop]; }}}return Target;
}
DeepClone(obj1,obj2)
obj2.card[2] = 'jian'
console.log(obj2,obj1)
Copy the codePlace replacement (one radish, one pit)
- I didn’t think there was a better way to do it, but when I looked at the problem, there was another condition that they didn’t use, and that wasAll the numbers in the array are in the range 0 to n-1, the associative array length is n.
- We do not need to create a new object or hash table, directly replace the original array nums[I] into the nums[I]. But if you put radish n back into radish pit N and you find radish n already in radish pit N, you’ve found a duplicate number in the array.
1.Start traversal initially, fill a pit before advancing nums[I]1 2 3 2The radish I0 1 2 3 坑 2.found0The one in the number pit1Radish number, put it back1Nums [I] = nums[I] = nums[I]2 1 3 2The radish I0 1 2 3 坑 3. 0The number pit is2Radish number, put it back in the same way2The pit nums [I]3 1 2 2The radish I0 1 2 3 坑 4. 0The number pit is3Radish number, put it back in the same way3The pit nums [I]2 1 2 3The radish I0 1 2 3 坑 5. 0The number pit is2Radish number, put it back2There was already one in the pit when counting the pit2Number radish, this will find the array in the occurrence of repeated numbers2theCopy the code - So we can solve this problem with no extra space and order n time.
- We do not need to create a new object or hash table, directly replace the original array nums[I] into the nums[I]. But if you put radish n back into radish pit N and you find radish n already in radish pit N, you’ve found a duplicate number in the array.
AC code
/ * * *@param {number[]} nums
* @return {number}* /
O(nlogn + n) = O(nlogn)
// function Divide (low,high,arr) {
// // console.log(arr,low,arr[low])
// var ref = arr[low];
// while (low < high) {
// while (low < high && arr[high] >= ref)
// high --;
// arr[low] = arr[high];
// while (low < high && arr[low] <= ref)
// low ++;
// arr[high] = arr[low]
/ /}
// arr[low] = ref;
// return low;
// }
// function Qsort (low,high,arr) {
// if (low < high) {
// var divide = Divide(low,high,arr);
// Qsort(low,divide - 1,arr);
// Qsort(divide + 1,high,arr);
/ /}
// }
var findRepeatNumber = function(nums) {
// 1. O(n^2)
// for (var i = 0; i < nums.length - 1; i ++) {
// for (var j = i + 1; j < nums.length; j ++) {
// if (nums[i] === nums[j])
// return nums[i];
/ /}
// }
O(nlogn + n) = O(nlogn)
// Qsort (0,nums.length - 1,nums);
// for (var i = 0; i < nums.length - 1; i ++) {
// if (nums[i] === nums[i + 1])
// return nums[i];
// }
// 3. Create an object (hash table), scan the array, check whether the current array value already exists (hash table)
// O(n)
// Object version
// var newObj = {};
// for (var i = 0; i < nums.length; i ++) {
// if (newObj.hasOwnProperty(nums[i])) {
// return nums[i]
// } else {
// newObj[ nums[i] ] = nums[i]
/ /}
// }
Nums [I] === = I; nums[I] === nums[I]] === nums[I] === I
// O(n + k), where k is the number of times in the while loop
// for (var i = 0; i < nums.length; i ++) {
// while (nums[i] ! == i) {
// if (nums[i] === nums[ nums[i] ]) {
// // returns the same number
// return nums[i];
/ /}
// // Exchange nums[I] with nums[nums[I]]
// var j = nums[i];
// nums[i] = nums[j];
// nums[j] = j;
/ /}
// }
var i = 0
while (i < nums.length) {
if(nums[i] ! == i) {if (nums[i] === nums[ nums[i] ]) {
// Return the same number
return nums[i];
}
// Exchange nums[I] with nums[I]
var j = nums[i];
nums[i] = nums[j];
nums[j] = j;
} else {
i ++
}
}
};
Copy the codeconclusion
- Before has not written the habit of solving the problem, brush the problem, after this review, found his problem solution is more clear, deepen their understanding, come on!
- I am participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to view the details of the campaign