In a JavaScript array how can I get the index of duplicate strings?
Example:
MyArray = ["abc","def","abc"]; //----> return 0,2("abc");
Another example:
My Array = ["abc","def","abc","xyz","def","abc"]
//----> return 0,2,5("abc") and 1,4("def");
I have no idea how to do this. Thanks in advance for your help!
Update 01/2022: It's not 2013 anymore, and many things have changed. I neither recommend modifying the prototype, nor is the approach in this answer the "best" as it requires several iterations over the array.
Here's an updated version of the original answer, retaining its spirit, as well as the original answer below.
function getDuplicates<T>(input: T[]): Map<T, number[]> {
return input.reduce((output, element, idx) => {
const recordedDuplicates = output.get(element);
if (recordedDuplicates) {
output.set(element, [...recordedDuplicates, idx]);
} else if (input.lastIndexOf(element) !== idx) {
output.set(element, [idx]);
}
return output;
}, new Map<T, number[]>());
}
Yet another approach:
Array.prototype.getDuplicates = function () {
var duplicates = {};
for (var i = 0; i < this.length; i++) {
if(duplicates.hasOwnProperty(this[i])) {
duplicates[this[i]].push(i);
} else if (this.lastIndexOf(this[i]) !== i) {
duplicates[this[i]] = [i];
}
}
return duplicates;
};
It returns an object where the keys are the duplicate entries and the values are an array with their indices, i.e.
["abc","def","abc"].getDuplicates() -> { "abc": [0, 2] }
indexOf and lastIndexOf in every iteration for every element, I would first check whether the element is already in duplicates. If it is you can directly push the index to the array. This saves some linear search time and you could even omit indexOf completely (just compare against i). Otherwise, using lastIndexOf is a nice approach!
[object Object] if you just output it like this. It's an object, you have to look at its properties! And no, you did not say you just want [0,2]. And that wouldn't make sense either, because what about your second example? How would you separate the indices for duplicates of different entries?Another less sophisticated approach:
Iterate over the whole array and keep track of the index of each element. For this we need a string -> positions map. An object is the usual data type to use for this. The keys are the elements of the array and the values are arrays of indexes/positions of each element in the array.
var map = {};
for (var i = 0; i < arr.length; i++) {
var element = arr[i]; // arr[i] is the element in the array at position i
// if we haven't seen the element yet,
// we have to create a new entry in the map
if (!map[element]) {
map[element] = [i];
}
else {
// otherwise append to the existing array
map[element].push(i);
}
// the whole if - else statement can be shortend to
// (map[element] || (map[element] = [])).push(i)
}
Now you can iterate over the map and remove all entries where the array value has a length of one. Those are elements that appear only once in an array:
for (var element in map) {
if (map[element].length === 1) {
delete map[element];
}
}
Now map contains a string -> positions mapping of all duplicate elements of the array. For example, if you array is ["abc","def","abc","xyz","def","abc"], then map is an object of the form
var map = {
'abc': [0,2,5],
'def': [1,4]
};
and you can process it further in any way you like.
Further reading:
This covers finding the indices efficiently:
var inputArray = [1, 2, 3, 4, 5, 6, 6, 7, 8, 9];
var encounteredIndices = {};
for(var i = 0; i < inputArray.length; i++)
if (encounteredIndices[inputArray[i]])
console.log(i); // Or add to some array if you wish
else
encounteredIndices[inputArray[i]] = 1;
0,2,5("abc") and 1,4("def")is not a valid return format and I could think of a number of details on how to return it. You should be more specific on what exactly you want to return.0,2,5and1,4, not without packing it into an object like in my answer. You could only return something like0,1,2,4,5, making it impossible to determine which entries they belong to or what entry is contained how often.