Skip to main content

3397. Maximum Number of Distinct Elements After Operations

Medium
Description

You are given an integer array nums and an integer k.

You are allowed to perform the following operation on each element of the array at most once:

  • Add an integer in the range [-k, k] to the element.

Return the maximum possible number of distinct elements in nums after performing the operations.

Example 1:​

Input: nums = [1,2,2,3,3,4], k = 2
Output: 6
Explanation: nums changes to [-1, 0, 1, 2, 3, 4] after performing operations on the first four elements.

Example 2:​

Input: nums = [4,4,4,4], k = 1
Output: 3 Explanation: By adding -1 to nums[0] and 1 to nums[1], nums changes to [3, 5, 4, 4].

Constraints:​

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

解題思路​

題目給的是一個整數陣列 nums 和一個整數 k，每個數最多可加上或減去一個介於 [-k, k] 的值（也可以不加減），目標是找出最多有幾個不同的數字。

  1. 首先由小到大排序 nums，並定義兩個變數 count 和 prev。
info

需要由小到大排序的原因是要確保貪婪演算法的策略正確
例如 [3,1,1], k=1，若不排序：

  1. 先處理 3， 根據貪婪演算法放 num - k = 2，
  2. 接下來處理 1 ，根據貪婪演算法放 prev + 1 = 3 ，但範圍是 [0,2]， 3 超出範圍不能放。

排序後 [1,1,3]：

  1. 前面的 1 可以放 0,1,2，根據貪婪演算法放 0
  2. 第 2 個 1 放 prev + 1 = 1
  3. 後面的 3 放 num - k = 3

這樣就可以塞更多不重複數。

nums.sort((a, b) => a - b);

let count = 0; // 記錄目前有幾個不同的數字
let prev = -Infinity; // 記錄上一個不重複的數字，初始值為負無限大，確保一定會比下一個數字小
  1. 逐步處理每個數，主要邏輯是找出這個數最小且不重複的可以放的值。
for (const num of nums) {
  let curr = Math.max(num - k, prev + 1);
  //   num - k 代表當前這個數最小能變成的值
  //   prev + 1 代表必須比前一個大才不重複
  //   Math.max 用以取兩個值中較大的，確保合規定又不重複
  if (curr <= num + k) {
    // 如果這個數可以放
    count++;
    prev = curr; // 更新 prev 來記錄上一個數字
  }
}
  1. 最後回傳 count 就是答案。
return count;

心得​

貪婪演算法