Java初心者の競技プログラミング日記

Dvorak配列でjavaを書いてます

マップを値でソートするメソッド

追記:もっと簡単な書きかたを見つけました
マップを値でソートする方法 - 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に要素を移し替えてあげることでソートできる。