🖋

LeetCode 26. Remove Duplicates from Sorted Array

に公開
Go
LeetCode
tech

はじめに

LeetCode 「26. Remove Duplicates from Sorted Array」の問題をGoで解きました。

問題

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

問題文

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. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

・Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
・Return k.

和訳
整数の配列 nums が昇順にソートされている場合、各要素が一意に一度だけ現れるように、重複をその場で取り除く。要素の相対順序は同じに保つ。次に nums の一意な要素の数を返す。

numsの一意な要素の数をkとすると、受理されるためには以下のことを行う必要がある：

・nums の最初の k 個の要素に、最初に nums に存在した順番で一意な要素が含まれるように、配列 nums を変更する。numsの残りの要素は、numsのサイズと同様に重要ではない。
・kを返す。

例

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

制約

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.

解答

ソート済みの配列から、一意な要素の数を求める問題です。
インプレースで解くという条件があります。

配列の要素を比較していくことになりますが、以下のようにappendを使い重複があったら削除するようにすると、
内部で要素のコピーが行われるため、効率が悪く追加のメモリを必要としてしまいます。

nums = append(nums[:i], nums[i+1:]...)

2ポインタのアプローチを使い、ユニークな値を前に詰めていくという方法で解くことが可能です。

コード

func removeDuplicates(nums []int) int {
	k := 1 // 最初の要素は必ず残る
	for i := 1; i < len(nums); i++ {
		if nums[i] != nums[k-1] {
			nums[k] = nums[i] // ユニークな値を前に詰める
			k++
		}
	}
	return k
}

この時、kはユニーク要素数であり、ユニークな値を書き込む場所のインデックスを示します。
iを進めながら、k-1の位置の値と比較してユニークな値が見つかった時点でkの位置にその値を入れて、kの値を増やしています。

計算量

  • 時間的計算量：O(n)
    • 一度ループするだけ
  • 空間的計算量：O(1)
    • 定数領域のみ
GitHubで編集を提案

Discussion