Leetcode) Remove Duplicates from Sorted Array


Top Interview Questions
Easy Collection
Link of Problem
LEVEL : 🌕 🌑 🌑 🌑 🌑 (最小)
Easy Collectionの最初の問題Remove Duplicates from Sorted Arrayを解いた.
英語で問題を書いたので、問題を説明するのから難しいです.
しかし、問題タイトルに示すように、これは送信アレイにおける重複数を解消する問題である.
最初に解いた時も3-4行のコードしか使わなかったが、後でRuntimeを減らすために他の方法を探した時も10行を超えなかった.
それでは問題解決の方向を説明しましょう

1𗞚𗞚第1の方法


Duplicateという単語を見るとSetを思い出します
ご存じのように、コレクションに配置されているすべての要素は、重複を解消するために保存されます.
したがって、Setを使用して重複データを除去し、.sorted()を使用することを選択した.
func removeDuplicates(_ nums: inout [Int]) -> Int {
    let numset = Set(nums)
    nums = numset.sorted()
    return nums.count
}
このようにコードを記述すると、Successになります.
しかし、Runtimeが勝った.

だから時間を短縮する旅が始まった.

2▼▼▼第1の方法


だから今回は設定せずにFOR MOONにしました
func removeDuplicates(_ nums: inout [Int]) -> Int {
    var numset: [Int] = []
    for n in nums {
        if !numset.contains(n) {
            numset += [n]
        }
    }
    nums = numset
    return nums.count
}

でも、以前よりもっと時間がかかりました・・・340ms..🥲

3ππ第1の方法


SetもFor Moonも違うと何になるんだろう私は長い間考えていたが、私は気にしていないことに気づいた.
それが「numset」
numsで処理すればいいだけで、numsetまでnumsとnumsetで値を往復移動しています.
だから私はコードを書いてnumsでしか処理できません.
func removeDuplicates(_ nums: inout [Int]) -> Int {
    guard nums.count > 1 else { return nums.count }
    var cnt = 0
    
    for index in 1..<nums.count {
        if nums[index] == nums[index-1]{
            cnt += 1
        } else {
            nums[index-cnt]=nums[index]
        }
    }
    return nums.count - cnt
}

結果は56ミリ秒!Setを使う時と30ミリ秒くらいしか差がありませんが、簡単な問題なので時間にはちょっと執着します.

🙃 inout


この問題を解くときに初めて見たINOUTの文法
Inoutキーを使用すると、変数のアドレス値に直接アクセスし、関数でパラメータを変更し、関数が終了した後も変更を続行できます.
そうですね関数でパラメータを変更するキーワードです.
前に学んだC,C++のポインタのキーワードを思い出します
上記のようにアドレス値を渡す必要があるので、C、C++と同じ&を使用して引数を指定する必要があります.
func start() {
    var ber = [1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 7]
    let num: Int = removeDuplicates4(&ber)
}
そうです.
アルゴリズムを学ぶと同時に学ぶことも多い.
# inout reference