JavaScript 查找已排序数组中的最后一个重复元素

在这个程序中，我们给定一个有重复元素的已排序数组，我们需要遍历for循环，返回数组中最后一个重复元素的索引和重复的数字。

问题介绍

在给定的问题中，我们需要找到已排序数组中的最后一个重复元素。重复元素指的是数字出现超过一次，所以我们给定一个已排序（递增顺序）的数组，我们要找到最后一个重复元素的索引和值。如果重复数字不存在，则返回”-1″。

例如，我们给定一个包含重复数字的已排序数组 –

Input: arr[] = {1, 2, 2, 3, 5, 5, 6, 7}
Output:
Last index: 5
Last duplicate value: 5

从给定的排序数组中，我们发现重复的值是2和5。而且5是索引5中的最后一个重复数字。因此，我们在最后的索引和最后的重复值中返回了5和5。如果数组中不存在重复值，则返回-1。让我们看一个示例 –

Input: arr[] = {1, 2, 3,5, 6, 7}
Output:
Last index: -1
Last duplicate value: -1

方法

我们已经看到了上面关于当前问题的示例。现在，让我们讨论一些方法。首先，我们将讨论的是对数组进行逆向遍历的方法，第二种方法是使用reduce()和indexOf()方法。让我们在下面的部分看一下它们。

方法1：对数组进行逆向遍历

在这里，我们首先比较数组中当前元素和上一个元素，因为我们是按照逆序遍历数组的。如果当前值和上一个值相同，这意味着我们找到了重复值，然后打印索引和重复元素。这将是最后的重复值，因为数组是有序的。如果没有重复值，则打印“-1”。

示例

JavaScript程序，打印有序数组中最后一个重复元素及其索引。

function dupLastIndex(array, num) {
   // if the size of array is less than or equal to 0
   if (num <= 0){
      document.write("-1");
   }

   // compare current and previous elements
   // if they matched return the index and value of the last duplicate number

   for (let i = num - 1; i > 0; i--){
      if (array[i] == array[i - 1]){
         console.log("Last index:" + i);
         console.log("Last duplicate value: " + array[i] );
         return;
      }
   }

   // If duplicate number is not present return -1
   console.log("-1");
}
let array = [1, 2, 2, 3, 5, 5, 6, 7];
let num = array.length;
dupLastIndex(array, num);

时间和空间复杂度

以上代码的时间复杂度是O(N)，其中N是排序数组的大小。因为我们只是从数组的末尾遍历了一次数组。而以上代码的空间复杂度是O(1)，因为我们不需要额外的空间，只使用了常数空间。

方法2：使用reduce()和indexOf()

我们已经看到了上述方法，其中所有的重复元素都相邻。这里我们使用reduce和indexOf方法的概念来获取数组中最后一个重复元素的索引。我们将从最后一个索引开始，并使用indexOf方法来检查给定当前元素的索引。由于indexOf()方法返回当前元素的第一个索引，意味着我们可以检查返回的索引和当前索引是否不匹配，如果不匹配，则可以将当前元素的索引作为答案返回。

示例

var arr = [1, 2, 2, 3, 5, 5, 6, 7];
function dupLastIndex(array) {
   var unique = arr.reduce((acc, iter, i)=>
   arr.indexOf(iter)!= i ? i : acc, -1);
   return unique;
}
let temp = dupLastIndex(arr);
if( temp != -1){
   console.log('Last index: ',temp);
   console.log('Last duplicate item : ',arr[temp])
} else {
   console.log('-1')
}

时间和空间复杂度

上述代码的时间复杂度为O(N*N)，其中N是数组的大小，因为我们遍历整个数组并且indexOf()方法在每次迭代中也可能需要O(N)的时间。给定代码的空间复杂度为O(1)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个JavaScript程序，用于在排序数组中查找最后一个重复元素。我们得到了一个有重复元素的排序数组，我们必须遍历for循环并返回数组中最后一个重复元素的索引以及重复的数字。我们使用了两种方法，它们的时间复杂度分别为O(N)和O(N*N)，并且两种方法的空间复杂度均为O(1)。