배열에 m 번 나타나는 고유 정수를 찾습니다.

이 배열의 다른 모든 정수는 n 번 나타납니다. 우리는 n>m 있습니다. 이 배열의 모든 요소는 정수입니다. O(N)에서 작동하는 알고리즘을 설계 할 수 있습니까? N은 공간 복잡성을 최소화하면서 어레이의 요소 수입니까? 최상의 경우 공간 복잡성은 O(log(m))으로 제한 될 수 있습니다.배열에 m 번 나타나는 고유 정수를 찾습니다.

특별한 경우는 n=2과 m=1입니다 (쉽습니다). 임의의 m 및 n을 처리 할 수있는 일반화 된 알고리즘이 있습니까?

감사

출처

2014-12-29 bozeng

"해시 테이블"이 포함 된 게시 된 솔루션은 시간 O (N * log2 (N/n)) 및 공간 O (N/n)을 필요로합니다. 더 나은 솔루션을 찾으면 솔루션을 게시 할 수 있습니까? – agershun

추가 질문 : 테이블의 정수는 순차적입니까 (이 예에서 [3,3,2,1,1]은 1에서 3까지입니다)? 이러한 유형의 경우 해시 테이블을 log2 (N/n) 대신 비용이 0 인 간단한 참조 배열로 대체 할 수 있습니다. – agershun

아니요 순차적이 아니라 매우 무작위입니다. – bozeng

당신은 발생의 수와 배열에 숫자를 매핑하는 해시 테이블을 사용할 수 있습니다. 배열을 반복하면서 각 숫자의 발생 횟수를 증가시킬 수 있습니다. 그런 다음 해시 테이블을 반복하여 n 번 발생하는 키를 검색 할 수 있습니다.

출처

2014-12-29 01:55:25

해시 테이블 검색의 경우 O (로그 N)을 추가해야하므로 O (N * log N)가됩니다 – agershun

무제한 메모리가 있으면 해시 테이블을 다음과 같이 거대한 배열 크기로 대체 할 수 있습니다. M (max (all number)) – agershun

해시 테이블에서 요소를 검색하면 O (N)이므로 알고리즘은 O (2N)이며 O (N)입니다. –

아래 사항이 귀하가 찾고있는 것일 수 있습니다. 기본적으로, 당신은 한 번만 정수 값과 배열을 occurrence.you 루프의 수와 같은 값으로 키를 사용하여지도를 작성하고 언제든지 숫자가 두 번 이상 발생, 당신은 수

public static void findCount (int[] array,int m, int n){ 

    if(m>n){ 
     thrown new IllegalArgumentException("m is greater than n"); 
    } 
    Map<Integer,Integer> intCount = new HashMap<Integer,Integer>(); 

     for(int i = 0; i<array.length; i++){ 
     if (!intCount.containsKey(array[i])) intCount.put(array[i], 0); 
     intCount.put(array[i], intCount.get(array[i]) + 1); 
    } 

    for (Map.Entry<String,Integer> entry : words.entrySet()) { 
      Integer key = entry.getKey(); 
      Integer value = entry.getValue(); 
      if(value==m){ 
      System.out.println("Value "+key+" Occurs "+value+" times"); 
    }    
    } 
}

출처

2014-12-29 01:56:30 sparrow

intCount.get (ind_words [i]) +1) O (log2 N)에 대한 비용 – agershun

"intCount.get (array [i]) + 1"이고 오른쪽에서 말하는 내용이 O (n) – sparrow

메인주기 비용 O (N)을 잊어서 합계는 O (N * log2N)입니다. – agershun

경우]의 증가 배열의 길이가 m보다 큰 경우 배열의 임의의 요소를 피벗합니다. 길이가 m (mod n) 인 배열의 절반을 찾아 그 절반을 반복합니다.

예상 런타임 O (N)이며 추가 저장 O (1)가 필요합니다.

출처

2014-12-29 08:01:52

흥미로운 아이디어. 최악의 경우는 O (N)보다 나쁠 것입니다. –

케이스 N = 2, m = 1이면이 아이디어는 함께로 (모듈로 n에게) 요소의 수를 카운트함으로써 일반화 될 수

배열 A. 함께 모든 숫자를 XOR 연산에 의해 수행 될 수있다 나는 조금 설정했다. 대답의 i 번째 비트가 설정된 경우에만 그 수가 0이 아닙니다.

O (log (n)) 추가 저장 영역을 사용하여 솔루션을 계산하는 O (N.log (max (A))) 방법을 제공합니다.

이 질문에 주어진 O (log (N)) 실행 시간과 O (log (m)) 저장소 복잡성을 달성하지는 않지만 흥미로운 접근 방법입니다.

출처

2014-12-30 08:45:37

배열에 m 번 나타나는 고유 정수를 찾습니다.

답변

관련 문제