スキップしてメイン コンテンツに移動

Pythonでリストの中から被っている値を見つけよう!!LeetCodeの解法例あり

リストの中から被っている値を見つけよう!!

という話。

見つけてその値を削除するなり、被っている値の数を数えるなり、被っている値は何なのかを返すなりは別にいいとして、個人的な方法をメモ代わりに取っておく。

基本

今回は考えやすいようにLeetCodeの問題を例に考えてみます。

問題

例えばこちら。
287. Find the Duplicate Number

難易度はMediumです。

問題としては与えられた数字のみのリストの中に1つだけ2つ存在する値があるのでそちらを探して欲しいという問題です。
例としては以下のような感じ。

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

Input: nums = [1,1,2]
Output: 1

解法

改良前

これの解放としてパッと思い浮かぶものとしては、二つのfor文で二つの値を比較しながら被っている値があれば行いたい処理を行う、というもの。

ただ、与えられたリストがソートされていないのでまずソートしないとその比較はできなくなります。

試しにPython3で書いてみました。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        ans = 0
        nums = sorted(nums)
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i] == nums[j]:
                    ans = nums[i]
        return ans
# Time Limit Exceeded

計算量はO(n^2)です。

試しに実行してみましたが、これでは時間切れです。

改良後

ではどうするのか?
この上のコードを少し改良するだけで実は計算量を大きく改善できます。

それが以下のコードです。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        if not nums:
            return
        ans,index = 0,1
        nums = sorted(nums)
	    for i in range(1,len(nums)):
	        if nums[i] == nums[index-1]:
	            ans = nums[i]
		    else:
		        index += 1
        return ans
# Runtime: 68 ms, faster than 55.74% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.6 MB, less than 78.10% of Python3 online submissions for Find the Duplicate Number.

二重for文の後のfor文を事前にインデックス値として宣言します。

for文の中で仮に値が被っていなければインデックスの値を1プラスするだけ。
被っていれば値をansに追加してインデックスの値を1プラスする。

これだけで計算量がO(n)になります。
そしてO(n^2)だと時間切れだったものが通るようになります。

こんな感じです。
単純な工夫ですが、これだけで計算量を削減できるので手軽に使えますね。

今回のメモはこんな感じ。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

Braveブラウザを使い始めて結構経った 設定 1 .同期ページを開く 2.QRコードの表示 3.iPhoneで読み取る Braveブラウザを使い始めて結構経った Google Domainsで独自ドメインを持っているBloggerをBrave Creatorsに登録した話。 この記事を書いた頃から僕はBraveしか使わなくなっちゃいましたね〜。 広告がないとネットサーフィンが捗りますし、Braveの直接クリエイターに貢献できるような仕組みが特に気に入っています。Blogger,ひいてはGoogle的にどうなんだって話もありそうですけど、ただのユーザなのでそんなのは気にせず便利なものは使います。 それで本題です。 タイトルのように今回同期機能を設定しました。 余計なことをしていたせいで少しハマったので設定ついでに誰かが困ったときに役に立つように設定方法を残しておこうかと思います。 ちなみにこちらの記事はPCの同期にiPhoneを追加するという設定方法についての解説です。iPhone→PCの同期方法などはまた別の話のようです。 設定 1 .同期ページを開く ブラウザのタブの右上にある上矢印のマークをクリックすると以下のような項目が表示されます。 こちらの同期という欄をクリックします。 すると以下のページが表示されます。 自動的に設定ページの中の同期欄が表示されるわけですね。 2.QRコードの表示 同期欄に同期済みのデバイスを管理という欄があるのでそちらをクリックします。 すると以下のようなページが表示されるのでそちらの中の新たなデバイスを追加、スマホ/タブレットという順にクリックしていくとQRコードが表示されます。 これでこのステップは完了です。 3.iPhoneで読み取る このQRコードをiPhoneで読み取っていく訳ですが、このQRコードはプリインストールされているQRコードで読み取っても正しく処理してくれません。 書いてある通り、iPhoneのBraveブラウザで読み取って上げる必要があります。 なのでひとまずiPhoneでBraveブラウザを開き、画面右下の**•••**という所をタップしてください。 すると上から二番目に歯車アイコンの設定が表示されますのでそちらをタップします。 初期表示で画面中部に表示さ

JavaのindexOf関数はナイーブ法で実装されているらしい

indexOf関数とは 実際のソースを見よう ナイーブ法ってなんぞや indexOf関数とは ドキュメント はここ。 indexOf の細かい使い方は説明はしないが、簡単にいうと二つの文字列を比較して重複する箇所がある場合にその開始部分のインデックスを返すというもの。 実際のソースを見よう どのように実装されているのかが気になったので jdkの中に存在するsrc.zipを解凍して確認してみることに。 public int indexOf ( String str ) { return indexOf ( str , 0 ) ; } public int indexOf ( String str , int fromIndex ) { return indexOf ( value , 0 , value . length , str . value , 0 , str . value . length , fromIndex ) ; } static int indexOf ( char [ ] source , int sourceOffset , int sourceCount , char [ ] target , int targetOffset , int targetCount , int fromIndex ) { if ( fromIndex >= sourceCount ) { return ( targetCount == 0 ? sourceCount : - 1 ) ; } if ( fromIndex < 0 ) { fromIndex = 0 ; } if ( targetCount == 0 ) { return fromIndex ; } char

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

Webスクレイピングとか 試していたらこれが突然出た。 macOS用公式インストーラーのPython 3.6でCERTIFICATE_VERIFY_FAILEDとなる問題 という記事に解決策が書いてあったが、 python.orgで配布されているmacOS用の公式インストーラーでインストールしたPython 3.6を使い、 urllib.request.urlopen() で https:// のWebページを取得しようとすると、以下のエラーが発生します。 で、このタイトルのエラーに当たっていたよう。 私の場合はPython3.8.5を使っていたので $ /Applications/Python\ 3.8/Install\ Certificates.command というコマンドをターミナルで叩くことで事なきをえた。 読んでないのが悪いとはいえこれはハマる人が多いんじゃなかろうか。