【LeetCode】 26. Remove Duplicates from Sorted Array 解答・解説【Python】

この記事は約4分で読めます。

 

問題

原文

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

内容

非降順でソートされた数値型の配列numsが与えられます。各要素が1度だけ出現するように重複を除外してください。要素同士の相対的な順序は同じ状態を保ってください。

いくつかの言語では配列の長さを変えられないため、配列numsの最初の部分に結果を入れなければなりません。

もし重複除外後にk個の要素がある場合、配列numsの最初のk個の要素は最終結果を持っていなければなりません。k個より先の要素は残していても問題ありません。

numsの配列の最初のk個に最終結果を入れて、kを返してください。

別の配列は用意してはいけません。

 

※正しくない可能性があります。

 

方針

・配列numsを全探索

・各要素の重複有無はpythonのスライスを使って調べる

・numsの最初の要素を重複除外後の結果で上書きしていく

解答

解答1

nums = [1,1,2]の場合

ループ処理の初回はnums[0:]となりますが、0番目のインデックス以前には要素はないため、nums[0]=1にi=1を代入し、kに1を加えます。→ nums = [1,1,2], k=1

2回目のループはk=1ですが、nums[:1]の範囲にi=1があるかを調べます。numsの最初の要素が1のためk=1と一致します。そのため何も起こりません。

3回目のループはk=1(2回目のループで何も起こらなかったため)となり、nums[:1]にi=2が含まれるかを調べます。その範囲に2は含まれないため、nums[1]にi=2を代入し、kに1を加えます。→nums = [1,2,2], k=2

最終的にnumsは[1,2,2]となり、kには2が入っており、重複を除外後の結果として返します。

 

補足・参考・感想

問題の内容を把握するのに苦戦しました。今でも腹落ちした感覚がなく、正しく理解できていないような気がします。わからない単語は途中DeepLなども使いながら英語の勉強も兼ねて行っています。

面接では、英語でのコミュニケーションに加えて、データ構造とアルゴリズムや、コンピュータサイエンスに関係する用語を英語で扱うことにも慣れる必要があるように思います。

今の内から少しずつ慣れていきたいなと思っています。

前:20. Valid Parentheses

次:27.Remove Element

LeetCode 解答・解説記事一覧

 

コメント