2024.1.31力扣每日一题——找出不同元素数目差数组
2024.1.31
- 题目来源
- 我的题解
- 方法一 哈希表+前后缀
题目来源
力扣每日一题；题序：2670
我的题解
方法一 哈希表+前后缀
从左到右计算前缀数组pre[i]表示nums[0,i]的不同元素个数；
从右到左计算后缀suff[i]表示nums(i,nums.length]的不同元素个数；
结果数组：pre[i]-suff[i]。
由于后续的后缀数组和结果数组可以复用前面的前缀数组，所以只需要定义一个数组
时间复杂度：O(n)
空间复杂度：O(n)
public int[] distinctDifferenceArray(int[] nums) {
int n=nums.length;
int[] pre=new int[n];
int[] suff=new int[n];
Set<Integer> set=new HashSet<>();
for(int i=0;i<n;i++){
set.add(nums[i]);
pre[i]=set.size();
}
set.clear();
for(int i=n-1;i>=0;i--){
if(i==n-1){
continue;
}
set.add(nums[i+1]);
pre[i]=pre[i]-set.size();
}
return pre;
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~