ゼロから始めるLeetCode Day53 「1365. How Many Numbers Are Smaller Than the Current Number」

概要

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

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

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

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

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」
次回
ゼロから始めるLeetCode Day54 「1290. Convert Binary Number in a Linked List to Integer」

Twitterやってます。

問題

1365. How Many Numbers Are Smaller Than the Current Number

難易度はEasy。
良い問題だったので書きます。

問題としては、配列numsが与えられます。
それらの配列の中の各要素が他の要素より大きい回数を導くようなアルゴリズムを設計してください、という問題です。
日本語的に難しいので例を見てみましょう。

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

解法

簡単な考え方としては、インデックスと紐付けて考えるというやり方があります。

numsをソートし、それをfor文の中で元々のインデックスで取り出し、配列に追加していってあげる、というものです。

例えば、例のnums = [6,5,4,8]であれば、
ソートした結果がnum = [4,5,6,8]となります。
その要素をインデックスで考えれば自ずと見えてきます。
num = [4,5,6,8]はインデックスは[0,1,2,3]となります。
これをnumsの順に置き換えると[2,1,0,3]となり、例と一致します。

この流れをPythonで書くとこんな感じになります。

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        ans = []
        num = sorted(nums)
        for i in range(len(nums)):
            ans.append(num.index(nums[i]))
        return ans
# Runtime: 92 ms, faster than 55.84% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.
# Memory Usage: 13.8 MB, less than 79.58% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.

もっと簡潔に書くと以下のようにも書けます。

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sorted_nums = sorted(nums)
        return [sorted_nums.index(num) for num in nums]
# Runtime: 100 ms, faster than 54.35% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.
# Memory Usage: 13.9 MB, less than 41.13% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.

考え方的には数え上げるのもありますが、この考え方の方がスマートだと思いました。
愚直に考えるのではなく、少し頭を捻ればスマートに解ける良い問題ですね。

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