在数组中查找第一个重复项并返回最小索引 [英] Finding first duplicate in an array and returning the minimal index
问题描述
因此问题如下:
给定一个仅包含从1到a.length范围内的数字的数组a,找到第一个重复的数字,其第二次出现的索引最小.换句话说,如果重复的数字多于1个,则返回其第二次出现的索引小于另一个数字的第二次出现的索引的数字.如果没有这样的元素,则返回-1.编写一个具有O(n)时间复杂度和O(1)额外空间复杂度的解决方案.
Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1. Write a solution with O(n) time complexity and O(1) additional space complexity.
我有一个解决方案,但是显然它的速度不够快,并且当数组中有超过一千个项目时会停顿.
I have a solution, but apparently it's not fast enough and stalls when there are over a thousand items in the array.
这就是我所拥有的:
function firstDuplicate(arr) {
let dictionary = {};
for(let i = 0, ii = arr.length; i < ii; i++) {
for(let z = i+1, zz = arr.length; z < zz; z++) {
if(arr[i] === arr[z]) {
if(dictionary.hasOwnProperty(arr[i])) {
if(dictionary[arr[i]] !== 0 && dictionary[arr[i]] > z) {
dictionary[i] = z;
}
} else {
dictionary[arr[i]] = z;
}
}
}
}
let answer = [];
for(key in dictionary) {
// [array number, position];
answer.push([key, dictionary[key]]);
};
if(answer.length > 0) {
return Number(answer.sort((a, b) => {
return a[1]-b[1];
})[0][0]);
}
return -1;
}
我认为将对象转换为数组,然后在答案完成后对数组进行排序会减慢整个功能.使用诸如 forEach
, map
和 sort
之类的内置JS方法(如我上面所做的那样),会使代码/功能的运行速度进一步降低.显然有一种更好,更准确的方法来执行此操作,因此我要求一些JS策划者来帮助我解决这个问题.
I think converting the object into an array and then sorting the array after the answers are complete slows down the whole function. Using built in JS methods like forEach
, map
and sort
(like I did above), slows the code/function down even more. There is obviously a better and more accurate way to do this, so I'm asking for some JS masterminds to help me out on this.
推荐答案
您可以继续将数字作为键添加到字典中,并以值作为索引,一旦在字典中找到重复的键,它就会返回其值.这将是O(n)的时间复杂度和O(n)的空间复杂度.
you can keep adding numbers to a dictionary as keys with values as their index, and as soon as you find a repeating key in the dictionary return its value. This will be O(n) time complexity and O(n) space complexity.
function firstDuplicate(arr) {
var dictionary = {};
for(var i = 0; i < arr.length; i++) {
if(dictionary[arr[i]] !== undefined)
return arr[i];
else
dictionary[arr[i]] = i;
}
return -1;
}
console.log(firstDuplicate([2, 3, 3, 1, 5, 2]));
由于数字在1到arr.length之间,因此可以在数组上进行迭代.对于每个arr [i],使用arr [i]作为索引,并使元素存在并且arr [arr [i]]为负,然后第一个arr [arr [i]]负返回arr [i].这样就可以实现O(1)的空间复杂度和O(n)的时间复杂度:
Since the numbers are between 1 to arr.length you can iterate on the array. For each arr[i] use arr[i] as index and make the element present and arr[arr[i]] negative, then the first arr[arr[i]] negative return arr[i]. This give O(1) space complexity and O(n) time complexity you can do this:
function firstDuplicate(arr) {
for(var i = 0; i < arr.length; i++) {
if(arr[Math.abs(arr[i])] < 0)
return Math.abs(arr[i]);
else
arr[Math.abs(arr[i])] = 0 - arr[Math.abs(arr[i])];
}
return -1;
}
console.log(firstDuplicate([2, 3, 3, 1, 5, 2]));
这篇关于在数组中查找第一个重复项并返回最小索引的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!