.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Plain Text
복사
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Plain Text
복사
Example 3:
Input: nums = [1,1]
Output: 1
Plain Text
복사
Example 4:
Input: nums = [1,1,2]
Output: 1
Plain Text
복사
Constraints:
•
1 <= n <= 105
•
nums.length == n + 1
•
1 <= nums[i] <= n
•
All the integers in nums appear only once except for precisely one integer which appears two or more times.
Follow up:
•
How can we prove that at least one duplicate number must exist in nums?
•
Can you solve the problem in linear runtime complexity?
My solution
숫자 안에 반복되는 숫자가 하나만 있습니다. 이 반복되는 숫자를 반환하십시오.
배열 인덱스를 수정하지 않고 일정한 추가 공간만 사용하여 문제를 해결해야 합니다.
소팅한 배열을 투포인터로 돌면서 mid를 업데이트하고 찾으려고 했다. mid가 indexOf(nums[mid])한 값과 다르거나 lastIndexOf(nums[mid])한 값과 다르거나, 둘다 다르거나 한 경우(왜냐하면 중복된 숫자는 2개 이상 나올수도 있으므로 둘다 다를 수 있다.) 이때의 nums[mid]를 리턴하려고 했다. 하지만 계속해서 틀리는 케이스가 나왔다.
test('TC9', () => {
expect(findDuplicate([14, 16, 12, 1, 16, 17, 6, 8, 5, 19, 16, 13, 16, 3, 11, 16, 4, 16, 9, 7])).toStrictEqual(16);
});
JavaScript
복사
그 이유는 다음 범위를 rt와 lt를 변경해서 지정해주어야 하는데 중복된 숫자들이 어디에 존재하는지 알 수 있는 조건이 없었다. 그래서 무작위로 rt와 lt를 변경해주는 방식이 되면 중복된 숫자들이 앞쪽에 몰려있는데도 lt와 rt가 뒷쪽으로 범위를 잡아서 해당 범위를 찾고 끝내버리는 문제였다.
그래서 다른 방식을 찾았다.
for (const x of nums) {
idx = Math.abs(x);
if (nums[idx] < 0) return idx;
nums[idx] *= -1;
}
JavaScript
복사
이와같이 배열을 돌면서 그 요소 하나하나를 인덱스로 사용했다. 이 인덱스를 다시 배열에 던져주면 이 값이 음수가 나올 수도 있는데, 이것은 이미 방문한 값임을 뜻했다. 따라서 nums[idx]는 매번 방문했으니 -1을 곱해서 배열 값 자체를 수정해주는 방식으로 공간복잡도를 줄일 수 있었다. 이렇게 배열의 내부값을 조금만 수정해주는 방식으로도 플래그의 효과를 볼 수 있다는 것을 다시한번 상기했다.
idx를 잡아서 배열에 그 idx에 대해 접근하는 부분은 이해하기 쉽지 않았다. Math.abs(x)를 한 이유는 nums의 값들을 방문할 때마다 음수화하고 있기 때문이다. 그리고 실제로 그 값을 인덱스로 사용해서 다른 값을 접근하는 것이기 때문에 해당 값이 음수여도 사용하는 것은 옳다.
또한 이렇게 인덱스 대용으로 배열의 요소를 사용할 수 있는 이유는 주어진 조건이 [1,n] 범위의 배열이기 때문이다. 이것이 연속적으로 주어진 배열이라면 해당 값들을 인덱스로 써서 접근하는 것은 for문으로 nums의 최댓값을 가지고 범위를 줘서 하나하나 찾아가는 것과 다를 바 없지만 더 깔끔하고 고차함수 배열 메서드를 사용할 수도 있어서 좋다고 생각된다.
또한 깔끔하게도 [1,1]과 같은 것도 처음에 1로서 인덱스 1을 방문해 -1로 만들어버리면 다음 방문도 인덱스 1을 방문하게 되어 음수이므로 답을 반환할 수 있다.
놀라운 것은 sort()를 하지 않았는데도 정상적으로 동작한다는 것이다.
왜냐?
결국엔 1~n까지를 방문하게 되어있는데 그걸 차례대로 1~n까지 방문하느냐 아니냐의 차이일 뿐이다. 하나하나 다 확인을 할 것이고 해당 값(인덱스)에 대한 배열 내의 값이 음수가 되어 있는 것을 발견하면 ok다.
함수형으론 아래와 같지만 좀더 느리다.
const findDuplicate = function (nums) {
return nums.reduce((acc, curr) => {
const idx = Math.abs(curr);
if (nums[idx] < 0) return idx;
nums[idx] *= -1;
return acc;
}, 0);
};
JavaScript
복사
소스코드
/**
* @param {number[]} nums
* @return {number}
*/
const findDuplicate = function (nums) {
let idx;
for (const x of nums) {
idx = Math.abs(x);
if (nums[idx] < 0) return idx;
nums[idx] *= -1;
}
};
test('TC1', () => {
expect(findDuplicate([1, 3, 4, 2, 2])).toStrictEqual(2);
});
// test('TC2', () => {
// expect(findDuplicate([3, 1, 3, 4, 2])).toStrictEqual(3);
// });
// test('TC3', () => {
// expect(findDuplicate([1, 1])).toStrictEqual(1);
// });
// test('TC4', () => {
// expect(findDuplicate([1, 1, 2])).toStrictEqual(1);
// });
// test('TC5', () => {
// expect(findDuplicate([1, 2, 2])).toStrictEqual(2);
// });
// test('TC6', () => {
// expect(findDuplicate([4, 3, 1, 4, 2])).toStrictEqual(4);
// });
// test('TC7', () => {
// expect(findDuplicate([1, 5, 5, 6, 2, 8, 4, 7, 5, 5])).toStrictEqual(5);
// });
// test('TC8', () => {
// expect(findDuplicate([4, 4, 17, 15, 2, 1, 19, 11, 12, 13, 3, 18, 4, 4, 5, 9, 7, 14, 4, 16])).toStrictEqual(4);
// });
// test('TC9', () => {
// expect(findDuplicate([14, 16, 12, 1, 16, 17, 6, 8, 5, 19, 16, 13, 16, 3, 11, 16, 4, 16, 9, 7])).toStrictEqual(16);
// });
JavaScript
복사
