找出不同元素数目差数组
难度:
标签:
题目描述
You are given a 0-indexed array nums of length n.
The distinct difference array of nums is an array diff of length n such that diff[i] is equal to the number of distinct elements in the suffix nums[i + 1, ..., n - 1] subtracted from the number of distinct elements in the prefix nums[0, ..., i].
Return the distinct difference array of nums.
Note that nums[i, ..., j] denotes the subarray of nums starting at index i and ending at index j inclusive. Particularly, if i > j then nums[i, ..., j] denotes an empty subarray.
Example 1:
Input: nums = [1,2,3,4,5] Output: [-3,-1,1,3,5] Explanation: For index i = 0, there is 1 element in the prefix and 4 distinct elements in the suffix. Thus, diff[0] = 1 - 4 = -3. For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1. For index i = 2, there are 3 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 3 - 2 = 1. For index i = 3, there are 4 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 4 - 1 = 3. For index i = 4, there are 5 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 5 - 0 = 5.
Example 2:
Input: nums = [3,2,3,4,2] Output: [-2,-1,0,2,3] Explanation: For index i = 0, there is 1 element in the prefix and 3 distinct elements in the suffix. Thus, diff[0] = 1 - 3 = -2. For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1. For index i = 2, there are 2 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 2 - 2 = 0. For index i = 3, there are 3 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 3 - 1 = 2. For index i = 4, there are 3 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 3 - 0 = 3.
Constraints:
1 <= n == nums.length <= 501 <= nums[i] <= 50
代码结果
运行时间: 29 ms, 内存: 16.0 MB
/*
* The goal is to calculate the difference between the number of distinct elements in the prefix and suffix of the array for each index.
* We will use Java Streams to process the array and compute the differences.
* We will use two sets to track distinct elements in the prefix and suffix.
*/
import java.util.*;
import java.util.stream.*;
public class DistinctDifferenceArrayStream {
public static int[] distinctDifferenceArray(int[] nums) {
int n = nums.length;
Set<Integer> prefixSet = new HashSet<>();
Set<Integer> suffixSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());
return IntStream.range(0, n)
.map(i -> {
prefixSet.add(nums[i]);
suffixSet.remove(nums[i]);
return prefixSet.size() - suffixSet.size();
})
.toArray();
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, 4, 5};
System.out.println(Arrays.toString(distinctDifferenceArray(nums1))); // Output: [-3, -1, 1, 3, 5]
int[] nums2 = {3, 2, 3, 4, 2};
System.out.println(Arrays.toString(distinctDifferenceArray(nums2))); // Output: [-2, -1, 0, 2, 3]
}
}
解释
方法:
该题解的核心思想是利用两次遍历的方法来分别计算前缀和后缀中不同元素的数量。首先，从数组的末尾开始向前遍历，使用一个集合(st)来存储遇到的元素，同时利用一个数组(sufCnt)记录从当前位置到数组末尾的不同元素的数量。在第二次遍历中，从数组的开始向后遍历，再次使用集合(st)来存储遇到的元素，并计算当前位置的前缀中不同元素的数量。然后利用前缀中的不同元素数量减去后缀中的不同元素数量，得到结果数组(res)的当前位置的值。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到从后向前遍历数组时，使用了一个集合(st)来更新sufCnt数组。请问如果数组nums中存在重复元素，这种方法是否仍然可以正确地计算出每个位置的后缀不同元素数量？
▷🦆
在题解的第二次遍历过程中，你提到了清空集合st后重新用于前缀的计算，这样做有什么特别的目的或好处吗？
▷🦆
题解实现的distinctDifferenceArray函数中，sufCnt数组的长度为len(nums) + 1，最后一个元素sufCnt[len(nums)]的值在计算中有被使用吗？如果没有，为什么会设计为len(nums) + 1？
▷🦆
在函数执行的最后，计算res数组时，为什么选择len(st) - sufCnt[i + 1]这种形式来计算不同元素数目差？是否有其他计算方式？
▷