マップを値でソートするメソッド
追記:もっと簡単な書きかたを見つけました
マップを値でソートする方法 - Java初心者の競技プログラミング日記
マップを値でソートするメソッド。上のメソッドは、マップを渡すと、値でソートされたマップが戻り値として返されるメソッド。下のメソッドは、ソートしたマップを出力するだけの戻り値なしのメソッド。
static Map<String,Integer> MapValueSort (Map<String,Integer> map, int n) { List<Integer> list = new ArrayList<>(map.values()); List<String> list2 = new ArrayList<>(); Map<String,Integer> map2 = new LinkedHashMap<>(); if (n==0) {Collections.sort(list);} else if (n==1) {Collections.sort(list,Comparator.reverseOrder());} for (int i=0; i<list.size(); i++) { for (Map.Entry<String,Integer> entry : map.entrySet()) { if (list.get(i)==entry.getValue() && list2.contains(entry.getKey())==false) { map2.put(entry.getKey(),entry.getValue()); list2.add(entry.getKey()); break; } } } return map2; } static void MapValueSortPrint (Map<String,Integer> map, int n) { List<Integer> list = new ArrayList<>(map.values()); List<String> list2 = new ArrayList<>(); if (n==0) {Collections.sort(list);} else if (n==1) {Collections.sort(list,Comparator.reverseOrder());} for (int i=0; i<list.size(); i++) { for (Map.Entry<String,Integer> entry : map.entrySet()) { if (list.get(i)==entry.getValue() && list2.contains(entry.getKey())==false) { System.out.println(entry.getKey()+" "+entry.getValue()); list2.add(entry.getKey()); break; } } } }
アルゴリズムは以下の記事のものとまったく同じ。
yukicoder No.628 Tagの勢い - Java初心者の競技プログラミング日記
メモリ消費量がすごそうだが、とりあえず動いてくれてすぐ使えるものを、というスタンスで作った。引数にはソートするマップ(LinkedHashMapを想定、TreeMapでも多分動く)と、0か1の数字を指定する。0なら昇順、1なら降順にソートされる。
以下は使用例である。
import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { Map<String,Integer> map = new LinkedHashMap<>(); map.put("a",5); map.put("c",1); map.put("e",4); map.put("d",3); map.put("b",2); //値で昇順ソート map = MapValueSort(map,0); System.out.println("<value ascending sort>"); MapPrint(map); System.out.println(); //値で降順ソート map = MapValueSort(map,1); System.out.println("<value descending sort>"); MapPrint(map); System.out.println(); } static Map<String,Integer> MapValueSort (Map<String,Integer> map, int n) { List<Integer> list = new ArrayList<>(map.values()); List<String> list2 = new ArrayList<>(); Map<String,Integer> map2 = new LinkedHashMap<>(); if (n==0) {Collections.sort(list);} else if (n==1) {Collections.sort(list,Comparator.reverseOrder());} for (int i=0; i<list.size(); i++) { for (Map.Entry<String,Integer> entry : map.entrySet()) { if (list.get(i)==entry.getValue() && list2.contains(entry.getKey())==false) { map2.put(entry.getKey(),entry.getValue()); list2.add(entry.getKey()); break; } } } return map2; } //マップを全列挙するメソッド static void MapPrint (Map<String,Integer> map) { map.forEach((key,value)->System.out.println(key+":"+value)); } } /*出力 <value ascending sort> c:1 b:2 d:3 e:4 a:5 <value descending sort> a:5 e:4 d:3 b:2 c:1 */
もし値が同じキーが複数あった場合は、元の並び順が保障される。つまり、
a:2
b:5
c:2
d:1
e:2
要素がこのような順番で格納されているLinkedHashMapを、このメソッドを使って降順にソートすると、
b:5
a:2
c:2
e:2
d:1
とソートされる。ソート前もソート後も、値が2であったa,c,eの順番は変化していない。
これを利用することで、「値で降順ソート、もし値が同じキーがあるならそれらのキーを昇順ソート」としたい場合は、コンストラクタ無しのTreeMap<>()をこのメソッドで降順ソートしてやればよく、あるいは「値で昇順ソート、もし値が同じキーがあるならそれらのキーを降順ソート」としたい場合も、TreeMap<>(Comparator.reverseOrder())をこのメソッドで昇順ソートしてやることで実現できる。
この記事ではずっと値でソートすることについて述べてきたが、もし値でなくキーでソートしたい場合は、最初からTreemapを使うか、あるいはLinkedHashMapなどからTreemapに要素を移し替えてあげることでソートできる。