同様の要素の発生数に応じてarraylistを並べ替える

Question

私は{2,2,1,1,1,5,4,4,4,4,4}を含むArrayListを持っており、各要素の出現回数に応じてソートしたい。だからそれは{4,4,4,4,4,1,1,1,2,2,5}を与えるでしょう。どこから始めますか？

import java.util.*; 

public class SortingL{ 

    public static void main(String[] args){ 

    ArrayList<Integer> list = new ArrayList<Integer>(); 

    Integer[] al = new Integer[] {2,2,1,1,1,5,4,4,4,4,4}; 
    list.addAll(Arrays.asList(al)); 

    sortL(list); 

    } 

    public static ArrayList<Integer> sortL(ArrayList<Integer> list){ 


    return list; 
    } 
} 

Answer 1

一つの解決策は、Collections#frequencyを使用することであろう。

List<Integer> list = Arrays.asList(2, 2, 1, 1, 1, 5, 4, 4, 4, 4, 4); 

list.sort(Comparator.comparing(i -> Collections.frequency(list, i)).reversed()); 

System.out.println(list); 

この意志出力予想結果：

[4、4、4、4、4、1、1、 1,2,2,5]

Answer 2

O（N）で行うことができます（メモリスペースのトレードオフはほとんどありません） ）

1. リスト項目
2. 今すぐ周波数
3. によって地図のキーとバケット番号を反復あなたの入力要素をハッシュマップ
4. 反復を作成し、ハッシュマップ
5. に各 要素の数を維持しますバケットを逆順に反復する

コード：

public List<Integer> frequencyBasedSort(int[] nums, int k) { 
    List<Integer>[] bucket = new List[nums.length + 1]; 
    Map<Integer, Integer> freqMap = new HashMap<>(); 
    for (int n : nums) { 
     freqMap.put(n, freqMap.getOrDefault(n, 0) + 1); 
    } 
    for (int key : freqMap.keySet()) { 
     int frequency = freqMap.get(key); 
     if (bucket[frequency] == null) { 
      bucket[frequency] = new ArrayList<>(); 
     } 
     bucket[frequency].add(key); 
    } 
    List<Integer> res = new ArrayList<>(); 
    for (int i = bucket.length - 1; i >= 0; i--) { 
     if (bucket[i] != null) { 
      res.addAll(bucket[i]); 
     } 
    } 
    return res; 
} 

Answer 3

最高のパフォーマンスを得るには、最初に値のカウントに値のMapを作成します。それをcountでソートし、配列を再構築します。

同じ回数で発生する異なる値が統合されるという効果があります。あなたはおそらく二次注文を指定したいと思うでしょうし、一貫して並べ替えられています。

例：

public static void main(String[] args) { 
    ArrayList<Integer> input = new ArrayList<>(Arrays.asList(2,2,1,1,1,5,4,4,4,4,4)); 
    ArrayList<Integer> sorted = sortL(input); 
    System.out.println(sorted); // prints: [4, 4, 4, 4, 4, 1, 1, 1, 2, 2, 5] 
} 
public static <V extends Comparable<V>> ArrayList<V> sortL(List<V> input) { 
    Map<V, ValueCount<V>> map = new HashMap<>(); 
    for (V value : input) 
     map.computeIfAbsent(value, ValueCount<V>::new).count++; 
    @SuppressWarnings("unchecked") 
    ValueCount<V>[] arr = map.values().toArray(new ValueCount[map.size()]); 
    Arrays.sort(arr); 
    ArrayList<V> sorted = new ArrayList<>(input.size()); 
    for (ValueCount<V> vc : arr) 
     for (int i = 0; i < vc.count; i++) 
      sorted.add(vc.value); 
    return sorted; 
} 
private static final class ValueCount<V extends Comparable<V>> implements Comparable<ValueCount<V>> { 
    final V value; 
    int count; 
    ValueCount(V value) { 
     this.value = value; 
    } 
    @Override 
    public int compareTo(ValueCount<V> that) { 
     int cmp = Integer.compare(that.count, this.count); // descending 
     if (cmp == 0) 
      cmp = that.value.compareTo(this.value); // descending 
     return cmp; 
    } 
}