2670.找出不同元素数目差数组

链接：2670.找出不同元素数目差数组
难度：Easy
标签：数组、哈希表
简介：返回 nums 的 不同元素数目差 数组。

题解 1 - cpp

• 编辑时间：2023-05-07
• 执行用时：48ms
• 内存消耗：90.9MB
• 编程语言：cpp
• 解法介绍：从左往右统计，从右往左统计。

class Solution {
public:
    vector<int> distinctDifferenceArray(vector<int>& nums) {
        unordered_set<int> s;
        int n = nums.size();
        vector<int> list1(n, 0), list2(n, 0), res(n, 0);
        for (int i = 0; i < n; i++) {
            s.insert(nums[i]);
            list1[i] = s.size();
        }
        s.clear();
        for (int i = n - 1; i >= 0; i--) {
            list2[i] = s.size();
            s.insert(nums[i]);
        }
        for (int i = 0; i < n; i++) {
            res[i] = list1[i] - list2[i];
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-05-07
• 执行用时：72ms
• 内存消耗：16.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:
        s = set()
        n = len(nums)
        list1 = [0] * n
        list2 = [0] * n
        res = [0] * n
        for i in range(0, n):
            s.add(nums[i])
            list1[i] = len(s)
        s.clear()
        for i in range(n - 1, -1, -1):
            list2[i] = len(s)
            s.add(nums[i])
        for i in range(0, n):
            res[i] = list1[i] - list2[i]
        return res

题解 3 - rust

• 编辑时间：2023-05-07
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn distinct_difference_array(nums: Vec<i32>) -> Vec<i32> {
        let mut s = std::collections::HashSet::<i32>::new();
        let n = nums.len();
        let mut list1 = vec![0; n];
        let mut list2 = vec![0; n];
        let mut res = vec![0; n];
        for i in 0..n {
            s.insert(nums[i]);
            list1[i] = s.len();
        }
        s.clear();
        for i in (0..n).rev() {
            list2[i] = s.len();
            s.insert(nums[i]);
        }
        for i in 0..n {
            res[i] = (list1[i] - list2[i]) as i32
        }
        res
    }
}

题解 4 - python

• 编辑时间：2024-01-31
• 执行用时：300ms
• 内存消耗：48.3MB
• 编程语言：python
• 解法介绍：记录下标，判断下标之间的最大距离。

class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:
        rdict = defaultdict(int)
        for num in nums: rdict[num] += 1
        cur = len(rdict)
        res = []
        ldict = defaultdict(int)
        for num in nums:
            rdict[num] -= 1
            if rdict[num] == 0: cur -= 1
            ldict[num] += 1
            if ldict[num] == 1: cur -= 1
            res.append(-cur)
        return res