投稿

ラベル(Medium)が付いた投稿を表示しています

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 = ...