시간 O (n)에서 배열에서 중복 요소 찾기
저는 면접에서이 질문을 받았는데 정답이 궁금했습니다.
0에서 n-1까지의 숫자 배열이 있으며 숫자 중 하나가 제거되고 해당 숫자를 복제하는 배열에 이미있는 숫자로 대체됩니다. 시간 O (n) 에서이 중복을 어떻게 감지 할 수 있습니까?
예를 들어,의 배열이 1,2,3,4될 것입니다 1,2,2,4.
시간 O (n 2 ) 의 쉬운 해결책은 중첩 루프를 사용하여 각 요소의 중복을 찾는 것입니다.
우리는 원래 배열을 가지고 있습니다 . 유형 int A[N];의 두 번째 배열 bool B[N]도 만듭니다 bool=false. 첫 번째 배열을 반복하고 B[A[i]]=truefalse이면 설정 하고 그렇지 않으면 bing!
이것은 O(n)시간과 O(1)공간 에서 할 수 있습니다 .
(알고리즘은 숫자가 알려진 범위의 연속 정수이기 때문에 작동합니다) :
벡터를 한 번 통과하여 모든 숫자의 합과 모든 숫자의 제곱의 합을 계산합니다.
에서 모든 숫자의 합을 뺍니다 N(N-1)/2. 이것을 호출하십시오 A.
에서 제곱의 합을 뺍니다 N(N-1)(2N-1)/6. 이것을로 나눕니다 A. 결과를 호출하십시오 B.
제거 된 번호는 (B + A)/2이고 교체 된 번호는 (B - A)/2입니다.
예:
벡터는 [0, 1, 1, 2, 3, 5]다음과 같습니다.
N = 6
벡터의 합은 0 + 1 + 1 + 2 + 3 + 5 = 12입니다. N (N-1) / 2는 15입니다. A = 3.
제곱의 합은 0 + 1 + 1 + 4 + 9 + 25 = 40입니다. N (N-1) (2N-1) / 6은 55입니다. B = (55-40) / A = 5.
제거 된 숫자는 (5 + 3) / 2 = 4입니다.
대체 된 숫자는 (5-3) / 2 = 1입니다.
작동하는 이유 :
원래 벡터의 합은
[0, ..., N-1]입니다N(N-1)/2. 값a이 제거되고로 대체되었다고 가정합니다b. 이제 수정 된 벡터의 합은N(N-1)/2 + b - a. 에서 우리는 수정 된 벡터의 합을 빼면N(N-1)/2우리가 얻을a - b. 그래서A = a - b.마찬가지로 원래 벡터의 제곱합은입니다
N(N-1)(2N-1)/6. 수정 된 벡터의 제곱합은입니다 . 원래 합 개질 벡터의 제곱의 합을 감산하여 준다 동일하다, . 따라서이를 (즉, )로 나누면 .N(N-1)(2N-1)/6 + b2 - a2a2 - b2(a+b)(a-b)a - bAB = a + b지금
B + A = a + b + a - b = 2a및B - A = a + b - (a - b) = 2b.
추가 공간없이 O (N) 시간에 할 수 있습니다. 알고리즘 작동 방식은 다음과 같습니다.
다음과 같은 방식으로 배열을 반복합니다.
발견 된 각 요소에 대해 해당 색인 값을 음수로 설정하십시오. 예 : a [0] = 2. a [2]를 찾은 경우 값을 부정합니다.
이렇게하면 발생하도록 플래그를 지정합니다. 당신은 음수를 가질 수 없다는 것을 알고 있기 때문에 당신이 그것을 부정한 사람이라는 것도 알고 있습니다.
값에 해당하는 색인이 이미 음수 플래그로 지정되었는지 확인하고, 그렇다면 중복 된 요소를 얻습니다. 예 : a [0] = 2이면 a [2]로 이동하여 음수인지 확인합니다.
다음 배열이 있다고 가정 해 보겠습니다.
int a[] = {2,1,2,3,4};
첫 번째 요소 다음에 배열은 다음과 같습니다.
int a[] = {2,1,-2,3,4};
두 번째 요소 후에 배열은 다음과 같습니다.
int a[] = {2,-1,-2,3,4};
세 번째 요소에 도달하면 a [2]로 이동하여 이미 음수가 표시됩니다. 당신은 중복을 얻습니다.
어레이를 3 번 스캔합니다.
- 모든 배열 요소를 함께 XOR- >
A. 0에서 N-1까지의 모든 숫자를 함께 XOR->B. 이제A XOR B = X XOR DX는 제거 된 요소이고 D는 중복 요소입니다. - 에서 0이 아닌 비트를 선택합니다
A XOR B. 이 비트가 설정된 모든 배열 요소를 함께 XOR합니다 ->A1. 이 비트가 설정된 0에서 N-1까지의 모든 숫자를 함께 XOR합니다->B1. 이제A1 XOR B1 = X또는A1 XOR B1 = D. - 한 번 더 배열을 스캔 찾아보십시오
A1 XOR B1. 발견되면 이것은 중복 요소입니다. 그렇지 않은 경우 중복 요소는A XOR B XOR A1 XOR B1입니다.
HashSet이미 본 모든 숫자를 유지 하려면 a 를 사용하십시오 . (상각) O(1)시간에 작동 하므로 합계는 O(N).
BitSet을 사용하는 것이 좋습니다. 우리는 N이 배열 인덱싱에 충분히 작다는 것을 알고 있으므로 BitSet은 합리적인 크기가 될 것입니다.
배열의 각 요소에 대해 해당 값에 해당하는 비트를 확인하십시오. 이미 설정된 경우 중복입니다. 그렇지 않은 경우 비트를 설정하십시오.
해시 테이블을 사용하십시오. 해시 테이블에 요소를 포함하는 것은 O (1)입니다.
@rici는 시간과 공간 사용에 대해 옳습니다 : "이것은 O (n) 시간과 O (1) 공간에서 할 수 있습니다."
그러나 질문은 더 넓은 요구 사항으로 확장 될 수 있습니다. 중복 번호가 하나만있을 필요는 없으며 번호가 연속적이지 않을 수 있습니다.
OJ는 여기에 이렇게 넣습니다 . (참고 3은 분명히 좁힐 수 있습니다)
각 정수가 1과 n (포함) 사이 인 n + 1 개의 정수를 포함하는 배열 nums가 주어지면, 적어도 하나의 중복 숫자가 존재해야 함을 증명하십시오. 중복 번호가 하나만 있다고 가정하고 중복 번호를 찾으십시오.
노트 :
- 어레이를 수정해서는 안됩니다 (어레이가 읽기 전용이라고 가정).
- 상수 O (1) 추가 공간 만 사용해야합니다.
- 런타임 복잡성은 O (n2)보다 작아야합니다.
- 배열에는 중복 번호가 하나만 있지만 두 번 이상 반복 될 수 있습니다.
이 질문은 Floyd의주기 찾기 알고리즘을 사용하여 Keith Schwarz 가 매우 잘 설명하고 답변 했습니다 .
이 문제를 해결하기 위해 사용해야하는 주요 트릭은 0에서 n-2 범위의 n 개 요소 배열이 있기 때문에 배열이 {0, 1, 집합에서 함수 f를 정의하는 것으로 생각할 수 있음을 알아 차리는 것입니다. ..., n-1} 자체에. 이 함수는 f (i) = A [i]로 정의됩니다. 이 설정이 주어지면 중복 된 값은 f (i) = f (j)가되는 한 쌍의 인덱스 i! = j에 해당합니다. 따라서 우리의 과제는이 쌍 (i, j)을 찾는 것입니다. 일단 우리는 f (i) = A [i]를 선택하여 중복 된 값을 쉽게 찾을 수 있습니다.
그러나 우리는이 반복되는 가치를 어떻게 찾을 수 있습니까? 이것은 사이클 감지라고하는 컴퓨터 과학에서 잘 연구 된 문제임이 밝혀졌습니다. 문제의 일반적인 형태는 다음과 같습니다. 함수 f가 주어집니다. x_i 시퀀스를 다음과 같이 정의하십시오.
x_0 = k (for some k)
x_1 = f(x_0)
x_2 = f(f(x_0))
...
x_{n+1} = f(x_n)
f가 도메인에서 자신으로 매핑된다고 가정하면이 함수는 세 가지 형식 중 하나를 갖습니다. 첫째, 도메인이 무한하다면 시퀀스는 무한히 길고 반복되지 않을 수 있습니다. 예를 들어 정수의 함수 f (n) = n + 1에는이 속성이 있습니다. 어떤 숫자도 중복되지 않습니다. 둘째, 시퀀스는 폐쇄 루프 일 수 있습니다. 즉, i가 있으므로 x_0 = x_i가됩니다. 이 경우 시퀀스는 일부 고정 된 값 집합을 무기한 순환합니다. 마지막으로 시퀀스는 "로 모양"이 될 수 있습니다. 이 경우 시퀀스는 다음과 같습니다.
x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
^ |
| |
+-----------------------+
즉, 시퀀스는 순환에 들어가는 요소의 체인으로 시작하여 무한 순환합니다. 시퀀스에서 도달하는주기의 첫 번째 요소를주기의 "진입"으로 표시합니다.
def findDuplicate(self, nums):
# The "tortoise and hare" step. We start at the end of the array and try
# to find an intersection point in the cycle.
slow = 0
fast = 0
# Keep advancing 'slow' by one step and 'fast' by two steps until they
# meet inside the loop.
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Start up another pointer from the end of the array and march it forward
# until it hits the pointer inside the array.
finder = 0
while True:
slow = nums[slow]
finder = nums[finder]
# If the two hit, the intersection index is the duplicate element.
if slow == finder:
return slow
하나의 작업 솔루션 :
숫자가 정수라고 가정
[0 .. N] 배열 생성
int[] counter = new int[N];
그런 다음 읽기를 반복하고 카운터를 증가시킵니다.
if (counter[val] >0) {
// duplicate
} else {
counter[val]++;
}
이것은 O(n)시간과 O(1)공간 에서 대안적인 해결책입니다 . 그것은 유사하다 RICI의 . 이해하기가 조금 더 쉽지만 실제로는 더 빨리 넘칠 것입니다.
X누락 된 숫자와 R반복되는 숫자가 되자 .
숫자가에서 온 것으로 가정 할 수 있습니다
[1..n]. 즉, 0이 나타나지 않습니다. 실제로 배열을 반복하는 동안 0이 발견되었는지 테스트하고 발견되지 않으면 즉시 반환 할 수 있습니다.이제 다음을 고려하십시오.
sum(A) = n (n + 1) / 2 - X + R product(A) = n! R / X
0 product(A)을 A건너 뛰는 모든 요소의 곱은 어디에 있습니까 ? 우리는있는 두 개의 미지수에 두 개의 방정식이 X와이 R수학적으로 유도 할 수 있습니다.
편집 : 대중적인 요구에 따라 다음은 해결 된 예입니다.
설정하자 :
S = sum(A) - n (n + 1) / 2
P = n! / product(A)
그러면 우리의 방정식은 다음과 같습니다.
R - X = S
X = R P
다음으로 해결할 수 있습니다.
R = S / (1 - P)
X = P R = P S / (1 - P)
예:
A = [0 1 2 2 4]
n = A.length - 1 = 4
S = (1 + 2 + 2 + 4) - 4 * 5 / 2 = -1
P = 4! / (1 * 2 * 2 * 4) = 3 / 2
R = -1 / (1 - 3/2) = -1 / -1/2 = 2
X = 3/2 * 2 = 3
다음과 같이 진행할 수 있습니다.
- 선형 시간 정렬 알고리즘 (예 : 계수 정렬)을 사용하여 배열 정렬-O (N)
- 정렬 된 배열을 스캔하고 연속 된 두 요소가 같으면 중지합니다.-O (N)
public class FindDuplicate {
public static void main(String[] args) {
// assume the array is sorted, otherwise first we have to sort it.
// time efficiency is o(n)
int elementData[] = new int[] { 1, 2, 3, 3, 4, 5, 6, 8, 8 };
int count = 1;
int element1;
int element2;
for (int i = 0; i < elementData.length - 1; i++) {
element1 = elementData[i];
element2 = elementData[count];
count++;
if (element1 == element2) {
System.out.println(element2);
}
}
}
}
public void duplicateNumberInArray {
int a[] = new int[10];
Scanner inp = new Scanner(System.in);
for(int i=1;i<=5;i++){
System.out.println("enter no. ");
a[i] = inp.nextInt();
}
Set<Integer> st = new HashSet<Integer>();
Set<Integer> s = new HashSet<Integer>();
for(int i=1;i<=5;i++){
if(!st.add(a[i])){
s.add(a[i]);
}
}
Iterator<Integer> itr = s.iterator();
System.out.println("Duplicate numbers are");
while(itr.hasNext()){
System.out.println(itr.next());
}
}
우선 Scanner 클래스를 사용하여 정수 배열을 만듭니다. 그런 다음 숫자를 반복하고 숫자를 세트에 추가 할 수 있는지 확인합니다 (특정 숫자가 이미 설정되어 있지 않아야하는 경우에만 숫자를 추가하여 설정할 수 있습니다. 즉, 세트는 중복 된 번호를 추가하고 부울을 반환하는 것을 허용하지 않음을 의미합니다.) 중복 값 추가시 vale FALSE). 추가 할 수 없음은 중복 된 번호이므로 나중에 인쇄 할 수 있도록 중복 번호를 다른 세트에 추가합니다. 중복 번호가 여러 번 반복 될 수 있으므로 한 번만 추가 할 수 있기 때문에 중복 번호를 세트에 추가하고 있다는 점에 유의하십시오. 마침내 Iterator를 사용하여 세트를 인쇄합니다.
// 이것은 HashSet 접근 방식과 유사하지만 하나의 데이터 구조 만 사용합니다.
int[] a = { 1, 4, 6, 7, 4, 6, 5, 22, 33, 44, 11, 5 };
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
for (int i : a) {
map.put(i, map.containsKey(i) ? (map.get(i)) + 1 : 1);
}
Set<Entry<Integer, Integer>> es = map.entrySet();
Iterator<Entry<Integer, Integer>> it = es.iterator();
while (it.hasNext()) {
Entry<Integer, Integer> e = it.next();
if (e.getValue() > 1) {
System.out.println("Dupe " + e.getKey());
}
}
hashMap을 효율적으로 사용할 수 있습니다.
Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int x : a)
{
if (map.containsKey(x)) map.put(x,map.get(x)+1);
else map.put(x,1);
}
Integer [] keys = map.keySet().toArray(new Integer[map.size()]);
for(int x : keys)
{
if(map.get(x)!=1)
{
System.out.println(x+" repeats : "+map.get(x));
}
}
이 프로그램은 C # 기반이며 다른 프로그래밍 언어를 사용하여이 프로그램을 수행하려면 먼저 배열을 오름차순으로 변경하고 첫 번째 요소를 두 번째 요소와 비교해야합니다.
int[] array=new int[]{1,2,3,4,5,6,7,8,9,4};
Array.Sort(array);
for(int a=0;a<array.Length-1;a++)
{
if(array[a]==array[a+1]
{
Console.WriteLine("This {0} element is repeated",array[a]);
}
}
Console.WriteLine("Not repeated number in array");
- 배열 정렬 O (n ln n)
슬라이딩 윈도우 트릭을 사용하여 배열 O (n) 횡단
공간은 O (1)
Arrays.sort(input); for(int i = 0, j = 1; j < input.length ; j++, i++){ if( input[i] == input[j]){ System.out.println(input[i]); while(j < input.length && input[i] == input[j]) j++; i = j - 1; } }
테스트 케이스 int [] {1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7}
출력 1, 2, 3, 7
배열을 순회하고의 부호를 확인합니다. array[abs(array[i])]양수이면 음수로 만들고 음수이면 다음과 같이 인쇄합니다.
import static java.lang.Math.abs;
public class FindRepeatedNumber {
private static void findRepeatedNumber(int arr[]) {
int i;
for (i = 0; i < arr.length; i++) {
if (arr[abs(arr[i])] > 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else {
System.out.print(abs(arr[i]) + ",");
}
}
}
public static void main(String[] args) {
int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
findRepeatedNumber(arr);
}
}
참조 : http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
설명한대로,
You have an array of numbers from 0 to n-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number.
I'm assuming elements in the array are sorted except the duplicate entry. If this is the scenario , we can achieve the goal easily as below :
public static void main(String[] args) {
//int arr[] = { 0, 1, 2, 2, 3 };
int arr[] = { 1, 2, 3, 4, 3, 6 };
int len = arr.length;
int iMax = arr[0];
for (int i = 1; i < len; i++) {
iMax = Math.max(iMax, arr[i]);
if (arr[i] < iMax) {
System.out.println(arr[i]);
break;
}else if(arr[i+1] <= iMax) {
System.out.println(arr[i+1]);
break;
}
}
}
- O(n) time and O(1) space ;please share your thoughts.
This can be done in O(n) time and O(1) space. Without modifying the input array
- The idea is similar to finding the starting node of a loop in a linked list.
- Maintain two pointers: fast and slow
slow = a[0]
fast = a[a[0]]
- loop till slow != fast
- Once we find the loop (slow == fast)
- Reset slow back to zero
slow = 0
- find the starting node
while(slow != fast){
slow = a[slow];
fast = a[fast];
}
- slow is your duplicate number.
Here's a Java implementation:
class Solution {
public int findDuplicate(int[] nums) {
if(nums.length <= 1) return -1;
int slow = nums[0], fast = nums[nums[0]]; //slow = head.next, fast = head.next.next
while(slow != fast){ //check for loop
slow = nums[slow];
fast = nums[nums[fast]];
}
if(slow != fast) return -1;
slow = 0; //reset one pointer
while(slow != fast){ //find starting point of loop
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
Here is the simple solution with hashmap in O(n) time.
#include<iostream>
#include<map>
using namespace std;
int main()
{
int a[]={1,3,2,7,5,1,8,3,6,10};
map<int,int> mp;
for(int i=0;i<10;i++){
if(mp.find(a[i]) == mp.end())
mp.insert({a[i],1});
else
mp[a[i]]++;
}
for(auto i=mp.begin();i!=mp.end();++i){
if(i->second > 1)
cout<<i->first<<" ";
}
}
int a[] = {2,1,2,3,4};
int b[] = {0};
for(int i = 0; i < a.size; i++)
{
if(a[i] == a[i+1])
{
//duplicate found
//copy it to second array
b[i] = a[i];
}
}
참고URL : https://stackoverflow.com/questions/14944458/find-duplicate-element-in-array-in-time-on
'Development Tip' 카테고리의 다른 글
| Sourcetree의 .gitignore 파일이 작동하지 않습니다. (0) | 2020.11.25 |
|---|---|
| 초 단위로 주어진 시간 간격을 사람이 읽을 수있는 형식으로 변환 (0) | 2020.11.25 |
| Android ImageView : 너비 맞추기 (0) | 2020.11.25 |
| Rails 4 앱의 이름을 바꾸는 방법은 무엇입니까? (0) | 2020.11.25 |
| 루트 비밀번호를 null로 설정하는 방법 (0) | 2020.11.25 |