题目描述
给你一个下标从0
开始的数组nums
,数组长度为n
。
nums
的 不同元素数目差 数组可以用一个长度为n
的数组diff
表示,其中diff[i]
等于前缀nums[0, ..., i]
中不同元素的数目 减去 后缀nums[i + 1, ..., n - 1]
中不同元素的数目。
返回nums
的 不同元素数目差 数组。
注意nums[i, ..., j]
表示nums
的一个从下标i
开始到下标j
结束的子数组(包含下标i
和j
对应元素)。特别需要说明的是,如果i > j
,则nums[i, ..., j]
表示一个空子数组。
问题分析
可以先进行一次遍历,用哈希表存储数组中每个元素的个数。
然后第二遍遍历计算前缀和后缀只差。具体计算过程如下:
- 指针移动
- 哈希表中减去当前元素,若当前元素个数为0,则后缀不同元素个数减1
- 将当前元素加入一个集合
set
,集合元素个数即为前缀不同元素个数 - 计算前后缀元素个数之差,加入结果集
程序代码
class Solution {
public:
vector<int> distinctDifferenceArray(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> mp;
for(auto num : nums) {
mp[num]++;
}
unordered_set<int> st;
vector<int> res;
int t = mp.size();
for(auto num : nums) {
mp[num]--;
if(mp[num] == 0) t--;
st.insert(num);
res.push_back(st.size() - t);
}
return res;
}
};