주어진 정렬 (n + 1) 요소를 포함하는 nums 및 모든 요소는 1에서 n 사이입니다. 중복 요소가 하나만있는 경우 중복 번호를 찾습니다.
차례
예
입력:
숫자 = {1, 3, 4, 2, 2}
출력:
2
입력:
숫자 = {3, 1, 3, 4, 2}
출력:
3
중복 번호 찾기에 대한 순진한 접근 방식
방법 1 (Brute Force)
인덱스 0에서 배열을 탐색하고 모든 요소에 대해 앞의 배열 요소에서 반복되는지 확인합니다.
반복되면 중복 요소이고 그렇지 않으면 다음 요소에 대해 계속합니다.
시간 복잡성 = 의 위에2)
JAVA 코드
public class FindTheDuplicateElement {
private static int findDuplicate(int nums[]) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// For every element check if it is repeated in the elements ahead of it
for (int j = i + 1; j < n; j++) {
// If repeated, this is the duplicate element
if (nums[j] == nums[i])
return nums[i];
}
}
// No duplicate found
return -1;
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 2};
System.out.println(findDuplicate(nums));
// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}
C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(int *nums, int n) {
for (int i = 0; i < n; i++) {
// For every element check if it is repeated in the elements ahead of it
for (int j = i + 1; j < n; j++) {
// If repeated, this is the duplicate element
if (nums[i] == nums[j])
return nums[i];
}
}
// Duplicate not found
return -1;
}
int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;
// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);
return 0;
}
2 3
방법 2 (정렬)
배열을 오름차순으로 정렬하면 중복 요소가 서로 인접 해 있습니다.
정렬 된 배열을 탐색하고 중복 요소를 반환합니다.
시간 복잡성 = O (n 로그 (n))
JAVA 코드
import java. util. Arrays;
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Sort the array
Arrays.sort(nums);
// Check the adjacent elements
for (int i = 0; i < n - 1; i++) {
// If adjacent elements are equal, this is the duplicate element
if (nums[i] == nums[i + 1])
return nums[i];
}
// No duplicate found
return -1;
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 2};
System.out.println(findDuplicate(nums));
// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}
C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(int *nums, int n) {
// Sort the array
sort(nums, nums + n);
// Check the adjacent elements
for (int i = 0; i < n - 1; i++) {
// If adjacent elements are equal, this is the duplicate element
if (nums[i] == nums[i + 1])
return nums[i];
}
// Duplicate not found
return -1;
}
int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;
// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);
return 0;
}
2 3
중복 번호 찾기를위한 최적의 방법
방법 1 (해싱)
HashSet을 만들고 nums 배열의 모든 요소에 대해 현재 요소가 HashSet에 있으면 중복이고 그렇지 않으면 요소를 HashSet에 삽입합니다.
시간 복잡성 = O (N)
공간 복잡성 = O (N)
중복 번호 찾기를위한 JAVA 코드
import java.util.*;
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Create a HashSet
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
// If the HashSet contains the element, then this is the duplicate
if (set.contains(nums[i]))
return nums[i];
// Else add the element to the set
set.add(nums[i]);
}
// No duplicate found
return -1;
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 1, 2, 5};
System.out.println(findDuplicate(nums));
// Example 2
nums = new int[]{3, 1, 4, 2, 5, 5};
System.out.println(findDuplicate(nums));
}
}
중복 번호 찾기를위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(int *nums, int n) {
// Create a HashSet
unordered_set<int> set;
for (int i = 0; i < n; i++) {
// If the HashSet contains the element, then this is the duplicate
if (set.find(nums[i]) != set.end())
return nums[i];
// Else add the element to the set
set.insert(nums[i]);
}
// Duplicate not found
return -1;
}
int main() {
// Example 1
int nums[] = {1, 3, 4, 1, 2, 5};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;
// Example 2
int nums2[] = {3, 1, 5, 4, 2, 5};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);
return 0;
}
1 5
방법 2 (XOR)
XOR 속성 (X ^ X) = 0에 따라이 속성을 사용하여 위의 문제를 해결할 수 있습니다.
- 정수 X를 1에서 n까지 요소의 XOR로 초기화합니다. 여기서 nums 배열의 크기는 (n + 1)입니다.
- 다른 정수 Y를 0으로 초기화합니다.
- 배열을 가로 질러 Y를 (Y ^ nums [i])로 업데이트합니다. 즉, Y는 nums 배열의 모든 요소에 대한 XOR을 저장합니다.
- 중복 요소는 (X ^ Y)입니다.
시간 복잡성 = 의 위에), 두 번의 순회를 통해 하나는 X를 구축하고 하나는 Y를 위해
공간 복잡성 = O (1)
중복 번호 찾기를위한 JAVA 코드
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Initialise X as XOR of elements from 1 to n
// Size of nums is (n + 1), here represented as n
int X = 0;
for (int i = 1; i <= n - 1; i++)
X = (X ^ i);
// Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
int Y = 0;
for (int i = 0; i < n; i++) {
Y = Y ^ nums[i];
}
// Duplicate element is (X ^ Y)
return (X ^ Y);
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 4};
System.out.println(findDuplicate(nums));
// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}
중복 번호 찾기를위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(int *nums, int n) {
// Initialise X as XOR of elements from 1 to n
// Size of nums is (n + 1), here represented as n
int X = 0;
for (int i = 1; i <= n - 1; i++)
X = X ^ i;
// Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
int Y = 0;
for (int i = 0; i < n; i++)
Y = Y ^ nums[i];
// Duplicate element is (X ^ Y)
return (X ^ Y);
}
int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 4};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;
// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);
return 0;
}
4 3
방법 3 (사이클 감지)
위의 문제는 두 개의 포인터를 느리고 빠르게 사용하는 Linked List의 순환 찾기 알고리즘으로 해결할 수 있으며, 느린 포인터는 한 단계 씩 이동하고 두 단계 씩 빠르게 이동합니다.
예를 고려하십시오.
nums [] = {1, 3, 4, 2, 2}
- 두 포인터를 nums [0]만큼 느리고 빠르게 초기화합니다.
- slow = nums [slow] 및 fast = nums [nums [fast]]를 수행하는 반면 slow와 fast는 같지 않습니다.
- 2 단계 후에 slow를 nums [0]로 지정하고 느리고 빠른 포인터를 각각 한 단계 씩 이동합니다. 즉,
slow = nums [slow]
fast = nums [빠름]
느리고 빠르다는 것은 같지 않습니다. - 3 단계 후에는 느리고 빠름이 중복 요소를 가리 킵니다.
시간 복잡성 = O (N)
공간 복잡성 = O (1)
중복 번호 찾기를위한 JAVA 코드
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
//Initialize two pointers slow and fast as nums[0].
int slow = nums[0], fast = nums[0];
// Do slow = nums[slow] and fast = nums[nums[fast]]
// while slow and fast are not equal.
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// assign slow as nums[0]
slow = nums[0];
// Move slow and fast by one step each while slow and fast are not equal
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
// Both slow and fast points to the duplicate element
return fast;
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 4, 2};
System.out.println(findDuplicate(nums));
// Example 2
nums = new int[]{3, 1, 5, 4, 2, 5};
System.out.println(findDuplicate(nums));
}
}
중복 번호 찾기를위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(int *nums, int n) {
//Initialize two pointers slow and fast as nums[0].
int slow = nums[0], fast = nums[0];
// Do slow = nums[slow] and fast = nums[nums[fast]]
// while slow and fast are not equal.
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// assign slow as nums[0]
slow = nums[0];
// Move slow and fast by one step each while slow and fast are not equal
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
// Both slow and fast points to the duplicate element
return fast;
}
int main() {
// Example 1
int nums[] = {1, 3, 4, 4, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;
// Example 2
int nums2[] = {3, 1, 5, 4, 2, 5};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);
return 0;
}
4 5
