如何查找数组中各索引i右侧出现的不同元素的数量

实现思路 #

最优解法时间复杂度为O(n)，仅需一次倒序遍历即可完成，避免了对每个索引单独遍历右侧元素带来的O(n²)冗余开销：

• 从数组末尾往左遍历，维护一个哈希集合存储已经遍历过的元素（也就是当前索引右侧的所有元素）
• 每个索引对应的右侧不同元素数量，就是当前哈希集合的大小
• 计算完当前索引的结果后，将当前索引的元素加入哈希集合，供左侧索引计算使用

代码实现 #

如果需要匹配你给出的示例输出[2,2,1,0,0]，只需在计算时排除和当前索引值相同的元素即可，各语言实现如下：

Python 版本 #

def get_right_distinct_count(arr):
    length = len(arr)
    result = [0] * length
    seen = set()
    # 最后一个元素右侧无元素，默认值为0，从倒数第二个开始遍历
    for i in range(length - 2, -1, -1):
        seen.add(arr[i + 1])
        # 排除当前元素自身的值后统计数量
        result[i] = len(seen) - (1 if arr[i] in seen else 0)
    return result

# 测试用例
Arr = [7,7,3,2,3]
print(get_right_distinct_count(Arr)) 
# 输出：[2, 2, 1, 0, 0]

如果不需要排除当前元素自身，直接返回len(seen)即可，输出结果为[3, 2, 1, 1, 0]。

JavaScript 版本 #

function getRightDistinctCount(arr) {
    const length = arr.length
    const result = new Array(length).fill(0)
    const seen = new Set()
    for (let i = length - 2; i >= 0; i--) {
        seen.add(arr[i + 1])
        result[i] = seen.size - (seen.has(arr[i]) ? 1 : 0)
    }
    return result
}

// 测试
const Arr = [7,7,3,2,3]
console.log(getRightDistinctCount(Arr))
// 输出：[2, 2, 1, 0, 0]

内容的提问来源于stack exchange，提问作者Abhishek Namdeo