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) 空间复杂度工作。