[LeetCode] 2009. Minimum Number of Operations to Make Array Continuous

轉自LeetCode

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

• All elements in nums are unique.
• The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make nums continuous.

 

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Solution

看這題的tag有 binary search，但一開始不知道該怎麼解

看了一下其他人的解法，需要有一些前置步驟

首先，必須將 duplication 拿掉，並且要 sort 一下

以 [4, 2, 4, 5, 6]，要變成 [2, 4, 5, 6]

但要注意的是，必須保留原 array 的長度資訊，因為要讓  [4, 2, 4, 5, 6] 符合題意

[2, 4, 5, 6] 這個只是拿來計算用而已

那 [2, 4, 5, 6] 怎麼用，這時候就可以用 binary search

想法是，題意有說最大的數字，是最小數字 + nums.size - 1 

(注意，這邊的 nums.size 是  [4, 2, 4, 5, 6] 的長度，不是 [2, 4, 5, 6] )

先從 2 開始，可以用 binary search 在 [2, 4, 5, 6] 找到第一個不小於 2 + 5 - 1 = 6 的位置

最後的 right = 4

這時候代表的是，如果以 2 當作是最小值，也就是不替換 2 的狀況下

可以有 right - index = 4 - 0 = 4 個不重複的數字，且符合題意

那麼， operation = nums.size - 4 = 5 - 4 = 1，需要一個 operation

總結一下，就是可以在原有的 nums 裡面， 保留 2, 4, 5, 6 這四個數字，其他的必須替換掉

那因為不知道保留 2 當作最小值，是不是最佳解，接著繼續看 4

index = 1, 用 binary search 找第一個不小於 4 + 5 - 1 = 8 的位置，right = 4

那可以保留多少 unique number = right - index = 4 - 1 = 3 -> 保留 4, 5, 6 的意思

所需 operation = nums.size - unique number = 5 - 3 = 2

比把 2 當作最小數字還要多，所以不更新

也就是必須歷遍 [2, 4, 5, 6]，把每個數當作最小值的狀況算出來，取最小值

kotlin(參考解法)

	class Solution {
	fun minOperations(nums: IntArray): Int {
	val sortedNums = nums.toSet().toList().sorted()
	var ans = Int.MAX_VALUE
	for(i in sortedNums.indices) {
	val target = sortedNums[i] + nums.size - 1
	var left = 0
	var right = sortedNums.size
	// find the first number that bigger than target
	while(left < right) {
	val mid = left + (right - left) / 2
	if(sortedNums[mid] <= target) {
	left = mid + 1
	} else {
	right = mid
	}
	}
	val uniqueLen = right - i
	ans = Math.min(ans, nums.size - uniqueLen)
	}
	return ans
	}
	}

view raw minimum_number_of_operations_to_make_array_continuous.kt hosted with ❤ by GitHub