ArrayList - 가장 일반적인 정수 검색

Question

내 arrayList에 999 개의 숫자가 있습니다. 숫자 중 일부가 반복됩니다. 목록에서 가장 빈번한 번호를 찾고 싶습니다. 가장 효율적인 방법은 무엇입니까?

Answer 1

소수의 성능 향상 만이 상징적입니다.)

import java.util.*; 

public class Test 
{ 
    static AbstractMap.SimpleEntry<Integer, Integer> getMostFrequentN2(ArrayList<Integer> values) 
    { 
     ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> frequencies = new ArrayList<>(); 

     int maxIndex = 0; 

     main: 
     for (int i = 0; i < values.size(); ++i) 
     { 
      int value = values.get(i); 

      for (int j = 0; j < frequencies.size(); ++j) 
      { 
       if (frequencies.get(j).getKey() == value) 
       { 
        frequencies.get(j).setValue(frequencies.get(j).getValue() + 1); 

        if (frequencies.get(maxIndex).getValue() < frequencies.get(j).getValue()) 
        { 
         maxIndex = j; 
        } 

        continue main; 
       } 
      } 

      frequencies.add(new AbstractMap.SimpleEntry<Integer, Integer>(value, 1)); 
     } 

     return frequencies.get(maxIndex); 
    } 

    static AbstractMap.SimpleEntry<Integer, Integer> getMostFrequentNLogN(ArrayList<Integer> values) 
    { 
     ArrayList<Integer> tmp = new ArrayList(values); 

     Collections.sort(tmp); 

     AbstractMap.SimpleEntry<Integer, Integer> max = new AbstractMap.SimpleEntry<>(0, 0); 

     int current = tmp.get(0); 
     int count = 0; 
     for (int i = 0; i < tmp.size(); ++i) 
     { 
      if (tmp.get(i) == current) 
      { 
       count++; 
      } 
      else 
      { 
       if (count > max.getValue()) 
       { 
        max = new AbstractMap.SimpleEntry<Integer, Integer>(current, count); 
       } 

       current = tmp.get(i); 

       count = 1; 
      } 
     } 

     if (count > max.getValue()) 
     { 
      max = new AbstractMap.SimpleEntry<Integer, Integer>(current, count); 
     } 

     return max; 
    } 

    public static void main(String[] args) 
    { 
     ArrayList<Integer> numbers = new ArrayList(99); 

     for (int i = 0; i < 99; ++i) 
     { 
      numbers.add((int)(Math.random() * 10)); 
     } 

     System.out.println(numbers); 

     System.out.println(getMostFrequentN2(numbers)); 
     System.out.println(getMostFrequentNLogN(numbers)); 
    } 
} 

Answer 2

예, 천천히.

목록을 사용하여이를 수행 할 수 있습니다. 내부 목록에는 사용자가 본 숫자가 들어 있고 외부 목록의 색인은 발생 횟수입니다. 당신이 입력 목록을 처리 완료되면 그래서 가공 후 "1,2,1,3,1,2,3,4"당신이

[ [4], [2, 3], [1] ] 

있을 것입니다, 당신은 최고에 포함 된 마지막 내부 목록을 얻을 수 있습니다 이 경우 외부 목록의 인덱스는 [1]입니다. 해당 목록의 모든 요소는 최대 _ 생 수에 대해 연결됩니다.

Answer 3

정렬 된 목록을 읽음으로써 가장 많이 발생하는 목록 및 개수보다 정렬합니다.

는 0 필요 (N 로그 n)이 왼쪽에서 오른쪽으로 목록을 읽고 가장 지금까지 본 얼마나 자주

된 값을 기억

1 1 1 3 3 6 11 42 42 42 42 82 

을 분류

1 3 6 1 82 42 11 42 1 42 3 42 

시간

Answer 4

의견에서 썼 듯이 0에서 100까지 숫자를 읽습니다.
at EXT 파일, 당신이

int[] count = new int[101]; 
... 
count[numberJustRead]++; 
... 

하고 사용할 수 있도록 모든 숫자

int max = 0; 
int maxIndex = 0; //this is what you looking for 
for(int i = 0, k = count.length; i < k; i++){ 
    if(count[i] > max){ 
    max = count[i]; 
    maxIndex = i; 
    } 
} 

또는 어쩌면 같은 읽기 후 구아바의 여기에 당신이있는 경우 물론 다른 복잡성 (두 개의 간단한 구현이 Mulitset