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

Question

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

我的代码 -

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

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

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

Answer 2

注意 - 非常重要 - 数组必须排序才能工作：

这应该可以解决问题：

 var prevValue = "";

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

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

Answer 3

const makeUniqueAndCount = arr => {
  const uniqueKeysObject = {};

  arr.forEach(number => {
    uniqueKeysObject[number] = true;
  });

  return Object.keys(uniqueKeysObject).length;
};

此解决方案使用 javascript 中的对象。 javascript 对象的键始终是唯一的。然后你可以使用 javascript 对象原型的 keys 方法将它变成一个数组来获取它的长度。此解决方案也适用于未排序的数组。

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

How to get unique values from a sorted array with time complexity of O(n) or better without altering the original array

javascript

arrays

algorithm

time-complexity

data-structures