CODEWITHSUNDEEP
javascript
Andrés Santa María Norero
Andrés Santa María Norero

Reputation: 31

Merge sorted arrays and remove duplicates javascript

I came up with this in order to merge two sorted arrays and remove duplicates. I want to know if I can do better.

Any ideas?

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;
}

Upvotes: 3

Views: 594

Answers (5)

mgoetz
mgoetz

Reputation: 129

First of all, your code does not do, what you think it does. Try to run it with this case:

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

and you'll see what's wrong.

For most usecases with primitive data, you can go very well with native functionality, it does exactly what you are trying to achieve:

let uniqueArr = [];

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

But this wasn't your question, I assume. If the data is complex or just for fun we can think of other solutions.

There are many ways to do things: some are more time-intensive, some need more space. These are my ideas for this solution, feel free to correct or credit.

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

Alternative, merge the two arrays first, than sort em, than use a "reducing/cloning" function, or use a hash table. It would depend on characteristics of data and ressources at your disposal;

Upvotes: 0

Siddharth Jain
Siddharth Jain

Reputation: 880

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

Upvotes: 1

Kasmetski
Kasmetski

Reputation: 705

I would do it this way

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));

Upvotes: 0

Nikhil Aggarwal
Nikhil Aggarwal

Reputation: 28455

You can try this

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

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

Upvotes: 2

JonRed
JonRed

Reputation: 2971

If you're open to underscore.js, and it's great, then you could try something like _.union

http://underscorejs.org/#union

Upvotes: 0

Related Questions