목록에있는 기본 10 숫자의 대부분 항목을 찾으십시오.

Question

다음 순서로 같은 번호의 항목을 가장 많이 찾는 방법은 무엇입니까?

1,5,4,3,2,5,3,1,5,3,7,5,7 

이 경우 대답은 5입니다.

목록에 각 숫자를 추가 할 때 기울어 져 있으며 숫자가 이미 목록에 있으면 카운터가 증가합니다. 이 방법에서는 각 숫자에 대해 카운터가 있어야한다고 생각합니다. 어떤 사람이 쉽게 이해할 수있는 해결책은 무엇입니까? -

public class Main { 

    public static void main(String args[]){ 

     int[] numbers = {1,5,4,3,2,5,3,1,5,3,7,5,7,7,7,7,7};   
     int[] counterArray = new int[numbers.length]; 

     for (int i = 0; i < numbers.length; ++i){ 
      counterArray[numbers[i]] = counterArray[numbers[i]] + 1; 
     } 

     int maxNumber = 0; 
     for (int i = 0; i < numbers.length; ++i){ 
      if(counterArray[i] > counterArray[maxNumber]) 
      { 
       maxNumber = i; 
      } 
     } 

     System.out.println(maxNumber); 
    } 

} 

Answer 1

이 값은 0에서 9 사이의 값이 될 것이라는 것을 알고있을 때 O (n) 처리 시간을 제공합니다. 사용자가 이미 가지고있는 초기 배열을 세지 않음)은 counterArray = new int[10];

int[] numbers = {1,5,4,3,2,5,3,1,5,3,7,5,7}; 
//int[] counterArray = new int[10]; // use this if the max value of the in the array 'numbers' is known to be 9 
int[] counterArray = new int[numbers.length]; // Use this if the max value of the array is not known. 
// or we can quickly iterate O(n) operation to find the max value and use that 

for (int i = 0; i < numbers.length; ++i){ 
    counterArray[numbers[i]] = counterArray[numbers[i]] + 1; 
} 

int maxNumber = 0; 
for (int i = 0; i < numbers.length; ++i){ 
    if(counterArray[i] > countarArray[maxNumber]) 
    { 
     maxNumber = i; 
    } 
} 

Console.WriteLine("Number: " + maxNumber.ToString() + " occurs " + countarArray[maxNumber].ToString() + " times."); 

값의 수에 적합하게 배열을 작성 후, 최소 및 최대 값을 사용 O (N)을 발견하는 것이다 과도한 메모리 사용을 줄일 수있는 또 다른 방법 (최소 값에 의해 배열의 오프셋 위치 기억).

Answer 2

알고리즘 중 하나를 (

스테파니의 대답의 약간의 수정 만이 작품 : 나는 자바

를 사용하고 있는데이 경우

이 작동하지 않습니다 시도이다 O (n) 시간 복잡도 및 O (1) 메모리 복잡성) :

앞에서 말한대로 각 번호 (10 개의 카운터)를 입력하고 목록을 한 번 스캔합니다. C 코드 (O와 (N^2) 시간 복잡도 및 O (1) 메모리 복잡도)

//int the_given_array[n]; 

int counter[10]; 
int ix, result; 
memset(counter,0,10); 

for(ix=0; ix<n; ix++) counter[the_given_array[i]]++; 

result = 0; 
for(ix=1; ix<10; ix++) if(counter[ix]>counter[result]) result = ix; 

알고리즘 2 :

주 :이 하나가 있다면 제보다 더 이점이 없다 10 진수를 처리하십시오 (제한된 수)!

현재 대상 번호에 대한 카운터를 설정하고 개수를 계산하려면 목록을 스캔하십시오. 다른 번호를 세는 것 등등. 같은 숫자가 가장 많이 발생하는 동안 최대 값을 유지하십시오. 목록을 n 번 스캔해야합니다. 속도를 높이려면 각 번호를 병렬로 처리하기 위해 GPU 프로그래밍을 사용하는 것이 좋습니다.

Answer 3

알고리즘이 빠르기 때문에 제안 된 솔루션이 실제로 가장 빠릅니다. 0 사이즈 (10)의 배열을 초기화하고 단순히 :

약간의 평균 시간 최적화로

for (int i: arrayList) ++counterArray[i] 

, 당신은 단지 발견되는 가장 흔한 두 숫자의 실행 카운터를 유지 할 수 있으며, 가장 일반적인 경우 검색을 중지 두 번째 가장 일반적인 것보다 앞선 것보다 많은데, 여기서 검사 할 숫자의 수는 어디입니까?