ゼロから始めるLeetCode Day60「1481. Least Number of Unique Integers after K Removals」

# 概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

[Leetcode](https://leetcode.com/)

Python3で解いています。

[ゼロから始めるLeetCode 目次](https://qiita.com/KueharX/items/6ee2502c3b620c795b70)

前回
[ゼロから始めるLeetCode Day59 「1221. Split a String in Balanced Strings」](https://qiita.com/KueharX/items/9dd7c8c8238c32de9400)

今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

[Twitter](https://twitter.com/kueharx)やってます。

約2ヶ月分の記事が溜まりました。ここまで続いたことに自分でも驚いています。

# 問題
[1481. Least Number of Unique Integers after K Removals](https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/)

難易度はMedium。
最近追加されたかなり新しめの問題ですね。

問題としては、配列の`arr`と整数の`k`が与えられます。`k`個分の要素を配列から削除した後、ユニークな整数の数の最小値を求めるアルゴリズムを設計してください、という問題です。

少し分かりづらいので例を見てみましょう。

>Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

この例だと1個の要素は配列内に`4`しかありません。なので4を削除します。
残った要素は`5`のみになるためそのまま`5`を返します。

>Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

`4`と`2`を削除することは決まりますが、残りの1つは`1`と`3`のいずれかを削除します。`1`か`3`が残りますが、それらの内ユニークな数の長さ自体は`2`となるのでそれを返します。

# 解法

今回返すのは整数であり、配列についてはどう扱っても解答に影響がないので早いうちにソートしておくと分かりやすいと思いました。
例の` arr = [4,3,1,1,3,3,2]`であれば` arr = [1,1,2,3,3,4]`といった風にソートを行うと何を削除すれば良いかが一目瞭然になりますね。

さて、手っ取り早く書いてしまうと、今回の問題は、与えられた`k`と要素の個数を比較して仮に`k`が要素の個数以上であれば`k`から`k`+要素の個数を引き、そして引いた回数をカウントします。
そして、最終的に元のソートした配列の長さから引いた回数を引いてあげれば良いです。

ただ、これだけ書かれても正直分からないと思うので実際のコードを見てみましょう。

```Python
import collections

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        sorted_counts,removed_counts = sorted(Counter(arr).items(),key=lambda x: x[1]),0
        for keys,values in sorted_counts:
            if k >= values:
                k -= values
                removed_counts += 1
        return len(sorted_counts) - removed_counts
                
# Runtime: 496 ms, faster than 92.08% of Python3 online submissions for Least Number of Unique Integers after K Removals.
# Memory Usage: 32.9 MB, less than 33.33% of Python3 online submissions for Least Number of Unique Integers after K Removals.
```



PythonではcollectionsのCounterという便利なライブラリがあるのでひとまず各個数をカウントしてあげるとよいですね。

なお、例1の場合は以下のようになります。

```Python
Counter({5: 2, 4: 1})
```

そして、これを`key`の値でソートしてあげると以下のようになる。

```Python
[(4, 1), (5, 2)]
```


ちなみに、Pythonをあまり書かない方はぱっと見ソートの部分を

```Python
sorted_counts = sorted(Counter(arr))
# [4,5]
```

と書きたくなるかもしれないですが、この場合、出力が`[4,5]`となるため個数がなくなってしまうためNGです。

なお、Pythonのlambda式が出てきていますが、

```python
名前 = lambda 引数, 引数, ...: 式
```

といった形で書くことができます。
しかし、PEP8でPythonにおいてはlambda式は無名関数として書くことを推奨しているので、今回はそれに倣っています。

なお、今回の使い方は`sorted()`の引数として使っていますが、これは`sorted()`においてlambda式を使うと任意の関数を各要素に適用してその結果を元にソートできる、という性質を生かすためです。

もちろん`def`で関数を定義し、それを`key`に指定しても良いのですが、今回のように一度しか使わないような状況であれば、今回のような書き方の方が簡潔に書けます。

今回は問題が新しく、あまり回答者がいないせいか速さ的にも悪くないものができたのではないでしょうか。

今回はここまで。お疲れ様でした。