如何在不改变原始数组的情况下从时间复杂度为 O(n) 或更好的排序数组中获取唯一值

Question

我想在不改变原始数组的情况下计算给定数组中的唯一值，但解决方案必须在time complexity of O(n). 到目前为止，所有我见过的解决方案，有time complexity of O(n^2) 喜欢这里。我在解决方案的逻辑中找不到错误。我是数据结构和算法的新手，想要一个简单的解决方案。

我的代码 -

const countUniqueValues = (arr) =>{
    if(arr.length === 0){
        return console.log(arr.length);
    }else if(arr.length === 1){
        return console.log(arr.length);
    }

    const unique = [];
    let i = 0;
    for( let j = 1; j < arr.length; j++){
        if(arr[i] !== arr[j]){
            i ++;
            unique.push(arr[i]);
        }
    }
    return console.log(unique);
}

//test cases
countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4

错误的输出 -

[ 1 ]
[
  2, 3, 4,  4,
  4, 7, 7, 12
]
0
[ -1, -1, 0 ]

Answer 1

将数组转换为 Set ( O(n)) 并计算集合的大小：

const countUniqueValues = arr => new Set(arr).size;