Problem
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
class Solution { public int findDuplicate(int[] nums) { //switch every k with nums[k-1], if nums[k-1] is also k, then found it int i = 0; while (i < nums.length) { if (i > 0 && nums[i] == nums[i-1]) return nums[i]; while (i > 0 && nums[i] != i+1) { int j = nums[i]-1; if (nums[j] == nums[i]) return nums[i]; else { swap(nums, i, j); i--; } } i++; } return -1; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/72992.html
摘要:復雜度思路每次通過二分法找到一個值之后,搜索整個數(shù)組,觀察小于等于這個數(shù)的個數(shù)??紤],小于這個位置的數(shù)的個數(shù)應該是小于等于這個位置的。要做的就是像找中的環(huán)一樣,考慮重復的點在哪里??紤]用快慢指針。代碼把一個指針放回到開頭的地方 LeetCode[287] Find the Duplicate Number Given an array nums containing n + 1 in...
題目:Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number,...
摘要:如果的數(shù)字都只有一個,那么我們會形成一個閉合的環(huán)。如果有重復數(shù)字出現(xiàn)的話,如下這里就有一個的環(huán),就是重復數(shù)字如果到每個數(shù)字都只出現(xiàn)一次,在里的個數(shù)應該就是個數(shù)大于的話,前面的數(shù)字里就會有重復。 // 如果[1,n]的數(shù)字都只有一個,那么我們會形成一個閉合的環(huán)。 idx 1 2 3 4 val 3 1 4 2 1->3->4->2 這樣就是一個閉合的環(huán)。 如果有重復數(shù)字出現(xiàn)的話,如下:...
Problem Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate nu...
摘要:暴力法復雜度時間空間思路如果不用空間的話,最直接的方法就是選擇一個數(shù),然后再遍歷整個數(shù)組看是否有跟這個數(shù)相同的數(shù)就行了。二分法復雜度時間空間思路實際上,我們可以根據(jù)抽屜原理簡化剛才的暴力法。 Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is bet...
閱讀 3650·2021-09-22 15:15
閱讀 3555·2021-08-12 13:24
閱讀 1309·2019-08-30 15:53
閱讀 1816·2019-08-30 15:43
閱讀 1179·2019-08-29 17:04
閱讀 2792·2019-08-29 15:08
閱讀 1574·2019-08-29 13:13
閱讀 3084·2019-08-29 11:06