合并排序数组并去重 - JavaScript

Question

我想合并两个已排序的数组并删除重复项，以下是我的代码。请问是否还有更好的方法？

有什么建议吗？

var mergeArrays = function(arr1 , arr2){
var mergedArray = new Array();
var i = 0, j=0,k=0;
var prev = -1;
while(arr1.length  > i || arr2.length > j){
    if(arr1[i] == arr2[j]){
        mergedArray[k] = arr1[i];
        i++;
        j++;
    }else if(arr1[i] < arr2[j] || arr2[j] == undefined){
        mergedArray[k] = arr1[i];
        i++;
    }else{
        if(arr2[j]>prev) {
            mergedArray[k] = arr2[j];
        }
        j++;
    }

    prev = mergedArray[k];
    k++;

}

return mergedArray;
}

- Andrés Santa María Norero

---

如果这段代码是可用的（它实现了你想要的功能，没有错误），你可以尝试在codereview.stackexchange.com上发布它。那个网站是为了改进你的代码而设立的。 - LisaMM

Answer 1

你可以尝试这个。

var mergeArrays = function(arr1 , arr2){
    var mergedArray = arr1.concat(arr2);

    var uniqueArray = mergedArray.filter(function(elem, pos) {
        return mergedArray.indexOf(elem) == pos;
    });
    return uniqueArray;
} 

- Nikhil Aggarwal

Answer 2

function merge(...args) {
    return [...new Set(args.reduce((acc,val) => [...acc, ...val]))].sort();
} //Short and crisp solution to merge arrays, sort them and remove duplicates

- sid7747

Answer 3

首先，你的代码并没有做你认为它做的事情。尝试使用这个案例运行它：

array1 = [0,0,0,1,1,1,3,5,5,5,5,9];
array2 = [1,1,1,1,1,1];

你会看到问题所在。

对于大多数基本数据的用例，你可以很好地使用本地功能，它完全可以实现你想要达到的目的：

let uniqueArr = [];

uniqueArr = [...new Set ([...array1, ...array2])].sort();

但我想这不是你的问题。

如果数据很复杂或只是为了好玩，我们可以考虑其他解决方案。

有很多方法可以做事情：有些需要更多时间，有些需要更多空间。这是我对这个解决方案的想法，欢迎纠正或给予认可。

function binarySearch(arr, left, right, x){
    // fastest search in a sorted (!) array
    
    if (right >= l) {
        let mid = left + Math.floor((right - l) / 2);
  
        if (arr[mid] == x)
            return mid;
  
        if (arr[mid] > x)
            return binarySearch(arr, left, mid - 1, x);

        return binarySearch(arr, mid + 1, right, x);
    }
  
    // element is not present in array
    return -1;
}

function cloneArrayKeepUniqueOnly(array, array2){
    // array must be sorted, arg remains unmodified
    // keeps only unique elements from the array
    let uniqueOnly = [];

    for (let i = 0; i < array.length; i++ ){
        
        if (array[i] == array[i+1] ){
            i ++;
            continue; 
        } else if (array[i] != array[i-1] && binarySearch(array2, 0, array2.length, array[i]) == -1){
            
            uniqueOnly.push(array[i]);          
        }
    }
    
    return uniqueOnly;
}

function cloneArrKeepOneOfEach(array){
    // array must be sorted, arg remains unmodified
    // keeps one of every element from the array
    let oneOfEach = [];
    
    for (let i = 0; i < array.length; i++ ){
        
        if (array[i] == array[i+1] ){

            continue; 
        } else{
            oneOfEach.push(array[i]);
        }
    }
    
    return oneOfEach;
}

// main ---------------

let array1 = [0,0,0,0,1,1,2,3,4,5,5,5,5,6,7];
let array2 = [1,1,1,1,1,1,1,1];

let mergedArray_oneOfEach = [];
let mergedArray_onlyUniques = [];

let complementArr_uniques, complementArr; 

// uniques only --------------- start
mergedArray_onlyUniques = cloneArrayKeepUniqueOnly(array1, array2);
complementArr_uniques = cloneArrayKeepUniqueOnly(array2, array1); 

for (element of complementArr_uniques){
    mergedArray_onlyUniques.push(element);
}

console.log("mergedArray_onlyUniques: ", mergedArray_onlyUniques);
// uniques only --------------- end

//one of each ----------------start

mergedArray_oneOfEach = cloneArrKeepOneOfEach(array1);
complementArr = cloneArrKeepOneOfEach(array2);

while (i < mergedArray_oneOfEach.length){

    let searchIndex = binarySearch(complementArr, 0, complementArr.length-1, mergedArray_oneOfEach[i]);

    if (searchIndex != -1) {

        complementArr.splice(searchIndex, 1);
    } 
    i ++;
}

for (element of complementArr){
    mergedArray_oneOfEach.push(element);
}

console.log("mergedArray_oneOfEach: ", mergedArray_oneOfEach);

//one of each ----------------end

另一种方法是先合并这两个数组，然后对它们进行排序，接着使用“减少/克隆”函数或哈希表。具体取决于数据的特性和您可用的资源。

- mgoetz

Answer 4

如果你愿意尝试使用underscore.js，那么你可以试试像_.union这样的东西，它非常棒。

http://underscorejs.org/#union

- JonRed

Answer 5

我会这样做

function unique(array) {
    var a = array.concat();
    for(var i=0; i<a.length; ++i) {
        for(var j=i+1; j<a.length; ++j) {
            if(a[i] === a[j])
                a.splice(j--, 1);
        }
    }
    return a;
};
var array1 = ["...",",,,"];
var array2 = ["///", "..."];
var array3 = unique(array1.concat(array2));

- Kasmetski