Question

2453. Destroy Sequential Targets

中文文档

Description

You are given a 0-indexed array nums consisting of positive integers, representing targets on a number line. You are also given an integer space.

You have a machine which can destroy targets. Seeding the machine with some nums[i] allows it to destroy all targets with values that can be represented as nums[i] + c * space, where c is any non-negative integer. You want to destroy the maximum number of targets in nums.

Return_ the minimum value of _nums[i]_ you can seed the machine with to destroy the maximum number of targets._

 

Example 1:

Input: nums = [3,7,8,1,1,5], space = 2
Output: 1
Explanation: If we seed the machine with nums[3], then we destroy all targets equal to 1,3,5,7,9,... 
In this case, we would destroy 5 total targets (all except for nums[2]). 
It is impossible to destroy more than 5 targets, so we return nums[3].

Example 2:

Input: nums = [1,3,5,2,4,6], space = 2
Output: 1
Explanation: Seeding the machine with nums[0], or nums[3] destroys 3 targets. 
It is not possible to destroy more than 3 targets.
Since nums[0] is the minimal integer that can destroy 3 targets, we return 1.

Example 3:

Input: nums = [6,2,5], space = 100
Output: 2
Explanation: Whatever initial seed we select, we can only destroy 1 target. The minimal seed is nums[1].

 

Constraints:

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

Solutions

Solution 1: Modulo + Enumeration

We traverse the array $nums$ and use a hash table $cnt$ to count the frequency of each number modulo $space$. The higher the frequency, the more targets can be destroyed. We find the group with the highest frequency and take the minimum value in the group.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.

class Solution:
  def destroyTargets(self, nums: List[int], space: int) -> int:
    cnt = Counter(v % space for v in nums)
    ans = mx = 0
    for v in nums:
      t = cnt[v % space]
      if t > mx or (t == mx and v < ans):
        ans = v
        mx = t
    return ans

class Solution {
  public int destroyTargets(int[] nums, int space) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int v : nums) {
      v %= space;
      cnt.put(v, cnt.getOrDefault(v, 0) + 1);
    }
    int ans = 0, mx = 0;
    for (int v : nums) {
      int t = cnt.get(v % space);
      if (t > mx || (t == mx && v < ans)) {
        ans = v;
        mx = t;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int destroyTargets(vector<int>& nums, int space) {
    unordered_map<int, int> cnt;
    for (int v : nums) ++cnt[v % space];
    int ans = 0, mx = 0;
    for (int v : nums) {
      int t = cnt[v % space];
      if (t > mx || (t == mx && v < ans)) {
        ans = v;
        mx = t;
      }
    }
    return ans;
  }
};

func destroyTargets(nums []int, space int) int {
  cnt := map[int]int{}
  for _, v := range nums {
    cnt[v%space]++
  }
  ans, mx := 0, 0
  for _, v := range nums {
    t := cnt[v%space]
    if t > mx || (t == mx && v < ans) {
      ans = v
      mx = t
    }
  }
  return ans
}