ArrayList - 搜索最常見的整數

-2

我在我的arrayList中有999個數字，其中一些數字是重複的。我想找到列表中最頻繁的數字，那麼做到最有效的方法是什麼？ArrayList - 搜索最常見的整數

2013-01-05 Kingfu Chow

我不知道。你可以嗎？ – 2013-01-05 23:51:59

不使用hashmap是什麼意思？二叉搜索樹對你有好處嗎？ –

數值的範圍是已知的嗎？ – MrSmith42

這裏有不同的複雜性（當然，如果你有兩個簡單的實現只有少數幾個性能增益是象徵性的）：

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)); 
    } 
}

來源

2013-01-06 00:34:57 Pragmateek

是的，慢慢地。

你可以用List列表來做到這一點;內部列表包含您所看到的數字，外部列表的索引是出現次數。因此，處理後的「1,2,1,3,1,2,3,4」你會

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

一旦你完成處理輸入列表中，你可以得到由最高所含的最後名單內外部列表的索引，在這種情況下是[1]。該列表中的所有元素都與最大發生次數相關聯。

來源

2013-01-05 23:55:08

對列表進行排序，並通過讀取排序後的List來計算哪些發生最多。

需要0（N log n）的時間

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

分類

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

閱讀列表中從左至右和記住的最到目前爲止其價值被視爲以及多久

來源

2013-01-05 23:56:52 MrSmith42

我認爲，正如你在評論中寫的那樣，你讀取的數字從0到100
from 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

來源

2013-01-06 00:05:36

ArrayList - 搜索最常見的整數

回答

相關問題