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) 空間複雜度工作。