LeetCode - 3347

2026年1月6日

LeetCode 3347

解法

觀察

每個元素可轉換的範圍:
原值 nums[i] 可被轉為區間 [nums[i] - k, nums[i] + k]。
問題可轉換為：
在數線上找一個目標值，使得最多元素的區間能涵蓋該值。
目標值只會是nums中的值。
區間的重疊:
每個 nums[i] 對應一個區間 [nums[i] - k, nums[i] + k]。
若多個區間在某段區間重疊，代表這些區間可被轉成共同重疊區間內的值。
可轉換為：
期望這個重疊區間內的值，找到最多涵蓋這個值的區間。
每個區間使用最大值，尋找另一個區間的最小值，並且重疊了最多的區間。
操作次數限制:
原本就等於目標值的元素不需操作。

策略

將問題分為兩種案例:

考慮重複的目標值，存在於nums中:
每個nums[i]取得最左邊的區間和最右邊的區間，使用nums[l] + k >= nums[i]還有nums[i] >= nums[r] - k。
使用Sort和Sliding Window，每個nums[i]的區間可以從nums[i-1]的區間位移過來，計算量為線性。
最大頻率為:
min(r - l + 1 - current_count, numOperations) + current_count，
current_count是和當前數字相同數字的計數，也就是不用操作的計數。
使用hash map儲存num的count。
不考慮重複的目標值，每個區間的nums[i] + k找到另一個區間的nums[j] - k:
使用Sort和Sliding Window，每個nums[i]使用nums[i] + k找到最右邊的nums[j]，並且nums[i] + k >= nums[j] - k。
最大頻率為:
min(j - i + 1, numOperations)。
Complexity
Time: O(n * log(n))
Space: O(n)

程式碼

java

public int maxFrequency(int[] nums, int k, int numOperations) {
  Arrays.sort(nums);

  int res = 1;
  HashMap<Integer, Integer> num_to_count = new HashMap<>();
  // process 2
  for (int i = 0, j = 0; i < nums.length; i++) {
    int cur = nums[i], left1 = cur - k, right1 = cur + k;
    num_to_count.put(cur, num_to_count.getOrDefault(cur, 0) + 1);
    while (j < nums.length) {
      int num_j = nums[j], left2 = num_j - k, right2 = num_j + k;
      if (is_overlapping(left1, right1, left2, right2)) {
        j++;
      } else {
        break;
      }
    }
    res = Math.max(res, Math.min(j - i, numOperations));
  }

  // process 1
  for (int i = 0, start = 0, end = 0; i < nums.length; i++) {
    int cur = nums[i];
    while (start < i) {
      int start_right = nums[start] + k;
      if (start_right < cur)
        start++;
      else
        break;
    }
    while (end + 1 < nums.length) {
      int next_end_left = nums[end + 1] - k;
      if (next_end_left <= cur)
        end++;
      else
        break;
    }
    int cur_cnt = num_to_count.get(cur);
    res = Math.max(res, Math.min(end - start + 1 - cur_cnt, numOperations) + cur_cnt);
  }

  return res;
}

private boolean is_overlapping(int left1, int right1, int left2, int right2) {
  // num1 <= num2, left1 <= left2
  return left1 <= left2 && left2 <= right1;
}