Zenn
🐙

NeetCode 150 [Array & Hashing]:medium 6/6

に公開
array
neetcode
hashing
tech

NeetCodeのSolutionを書いていく

Longest Consecutive Sequence

問題概要

整数の配列numsが与えられます。
numsを使って最長な連続数値長を返しなさい。
連続とは、要素の配列で、それぞれの要素が必ず一つ前の要素より大きくなっているものです。
元の配列で連続である必要はありません。

  • 制約
    • 入力の配列は0以上1000以下
    • 数値は-10^9以上10^9以下

計算回数：O(n)
メモリ：O(n)
nはnumsの配列数

例

Input: nums = [2,20,4,10,3,4,5]
Output: 4

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

メモ

まずソートして、小さい方からカウントしていくか？
初期値として、連続数は0、現在値(cur_v)の初期値を10^10とかありえない数字にしておく。
初期値の場合は要素cur_vにいれ、連続数をカウントアップ。
次の数が現在地より一つ大きければcur_vに代入、連続数をカウントアップ。
これだと計算はソートのO(nlogn) + O(n) ≒ O(nlogn) になるので前提のO(n)をクリアできない。

つまりソートはできない。
一方でメモリは多めに設定してある。
ということはDPか？

各数字用のdictを用意しておく。
listはsetにする。
自分の数字がdictになければ自分のkeyにvalueとして1を代入。
自分の前後の数字がmapに存在するか確認する。
存在する場合でdictになければ1を代入。存在する場合は何もしない。
自分の前後の数字を加算した値を自分と存在するdictに代入する。
...どうもこれだとうまくいかないな。

わからないのでヒントを見た。
連続点の開始点だけ先に探して、その点を起点に連続数を構成する。というやり方が良いみたい。
開始点を探すのは、自分-1の数が存在しないことを確認すれば良い。
開始点の探索はO(n)でできる。
開始点が見つかった後は、その次の点、次の点、と探せば良いが、これはO(n)か？

from typing import DefaultDict, List, Set

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        def find_start(nums: Set[int]) -> Set[int]:
            starts = set()
            for n in nums:
                if n - 1 not in nums:
                    starts.add(n)
            return starts

        nums_set = set(nums)
        starts_set = find_start(nums_set)

        consecutive_nums: DefaultDict = DefaultDict(lambda: 0)
        for start in starts_set:
            search_num = start
            while True:
                if search_num in nums:
                    consecutive_nums[start] += 1
                    search_num += 1
                else:
                    break

        return 0 if not consecutive_nums else max(consecutive_nums.values())

計算オーダーについて

chatGptにきいてみたところ以下らしい。

  1. find_start() の計算量
def find_start(nums: Set[int]) -> Set[int]:
    starts = set()
    for n in nums:
        if n - 1 not in nums:
            starts.add(n)
    return starts

• nums の各要素 n について n - 1 not in nums を確認するため、O(1) のセット検索を行う。
• nums の全要素をループするため O(n)。

よって、find_start(nums) の計算量は O(n)。

  1. for start in starts_set: ループ
for start in starts_set:
    search_num = start
    while True:
        if search_num in nums:
            consecutive_nums[start] += 1
            search_num += 1
        else:
            break

• starts_set のサイズは高々 n（すべての要素がスタート要素となる最悪ケース）。
• while ループは、各スタート start から search_num をインクリメントしながら nums に含まれるか確認。
• すべての nums の要素を一度だけ訪れるため、合計で O(n)。

  1. max(consecutive_nums.values())
return 0 if not consecutive_nums else max(consecutive_nums.values())

• consecutive_nums.values() の最大値を取る処理は O(n)。

全体の計算量
• find_start(nums_set): O(n)
• for start in starts_set: ループ: O(n)
• max(consecutive_nums.values()): O(n)

よって、合計で O(n) + O(n) + O(n) = O(n) となります。

結論

このアルゴリズムの計算量は O(n) です。

Discussion