HashMapを使った配列の比較

Question

LeetCode で1051. Height Checkerという問題を解いています。

Example 1
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
heights: [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.
Example 2
Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights: [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.
Example3
Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights: [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.

という風に与えられた配列(Input heights)に対して、その配列が昇順で並べられた時と、元の配列とを比較して値が違う箇所の個数をOutputとして出力しろ、という問題です。

これをArraysortを使わずHashMapで行いたいのですが、いまいちうまく行っておりません。
Twoポインターの使い方が良くないのだと思いますが、どのように書くべきでしょうか。

class Solution {
    public int heightChecker(int[] heights) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i< heights.length; i++){
            map.put(heights[i], map.getOrDefault(heights[i], 0) + 1);
        }
        
        int result = 0;
        List keys = new ArrayList(map.keySet());
        
        for (int i = 0, curHeight = 0 ; curHeight < heights.length ; curHeight++) {
            if(map.get((int)keys.get(i)) > 0) {
                if(heights[curHeight] != (int)keys.get(i)){
                    result++;
                }
                map.put((int)keys.get(i), map.get((int)keys.get(i)) - 1);    
            }else{
                i++;
            }
        }
        return result;
    }
}

回答例として以下のようなコードがあり、こちらではint[101]を使っているのですが、上記では以下と同じことをHashMapで行いたいと考えております。

class Solution {
    public int heightChecker(int[] heights) {
        int[] heightToFreq = new int[101];
        
        for (int height : heights) {
            heightToFreq[height]++;
        }
        
        int result = 0;
        int curHeight = 0;
        
        for (int i = 0; i < heights.length; i++) {
            while (heightToFreq[curHeight] == 0) {
                curHeight++;
            }
            
            if (curHeight != heights[i]) {
                result++;
            }
            heightToFreq[curHeight]--;
        }
        
        return result;
    }
}

Answer 1

まずどういうアルゴリズムで進めるかをきちんと整理しましょう。
配列のソートをするのが手っ取り早いわけですが、それをせずにするわけですよね。
解答の場合は、ソートの代わりに、
0. 高さごとの度数分布を調べる
0. 低いほうから順に個数を見ていくと、左から順にその高さがその個数分並んでいることになる

とすることで、疑似的にソートをしていることになります。
質問者のコードでは、maisumakunさんの指摘通り、HashMapから得られるkeySetの順序の保証が無いため、
Listに突っ込んだ後に高さ順に並んでいる保証が取れません。

HashMapは、特定の順番で処理をするという目的には向かないので、違うものを使いましょう。
TreeMapが適しているかと思います。
higherEntryなどを駆使すれば、Listに詰めなおす必要もありません。

蛇足
Mapでのカウントは次のように書くとスマートです。

        for(int i = 0; i< heights.length; i++){
            map.merge(heights[i], 1, Integer::sum);
        }

Comments

[macaroni323]

ありがとうございました

Answer 2

List keys = new ArrayList(map.keySet());としていますが、keysの順序は保証されていないのではないでしょうか？

Comments

[maisumakun]

HashMap.keySetの返り値はSetですが、特段の順序の保証はなさそうです。

[macaroni323]

ありがとうございました