求创意设计分享的网站,做国产免费视频网站,镜像别人网站做排名的好处,模板公司题目
题目链接
分析
一种暴力的方法#xff0c;枚举数组所有数字#xff0c;分别计算当前元素前面不同的元素和后面不同的元素#xff0c;然后相减即可。这样的话太暴力#xff0c;前缀和后缀也需要分别遍历#xff1a;O(N*2)了。
我们来优化一下#xff1a; 根据这种…题目
题目链接
分析
一种暴力的方法枚举数组所有数字分别计算当前元素前面不同的元素和后面不同的元素然后相减即可。这样的话太暴力前缀和后缀也需要分别遍历O(N*2)了。
我们来优化一下 根据这种暴力方法我们可以利用一下 Set 的特性Set 集合里面每一个元素都是唯一的。 后续遍历数组记录每个后缀不同的不同元素的个数就是set的大小然后把元素放入 set 里面组成数组 sufCnt这就把当前元素i的后缀不同元素的个数求出来了 sufCnt[i]。 然后就是求 前元素i的前缀不同元素的个数其实和求后缀一样 防止多创建一个 set 集合我们直接把之前的 set 集合清空 。 正序遍历数组把元素放入 set 里面然后记录每个前缀不同的不同元素的个数就是set的大小然后减去 sufCnt[i]即可就是题目想要求的值。
代码
class Solution {public int[] distinctDifferenceArray(int[] nums) {int n nums.length;// 存放最终结果int[] res new int[n];// 存放后缀int[] sufCnt new int[n];SetInteger set new HashSet();for(int i n - 1;i 0;i --) {sufCnt[i] set.size();set.add(nums[i]);}// 清空 set 集合set.clear();for(int i 0;i n;i ) {set.add(nums[i]);res[i] set.size() - sufCnt[i];}return res;}
}
