Tenemos una array ordenada con elementos duplicados y tenemos que encontrar el índice del último elemento duplicado e imprimir el índice y también imprimir el elemento duplicado. Si no se encuentra tal elemento, imprima un mensaje.
Ejemplos:
Input : arr[] = {1, 5, 5, 6, 6, 7} Output : Last index: 4 Last duplicate item: 6 Input : arr[] = {1, 2, 3, 4, 5} Output : No duplicate found
Simplemente iteramos a través de la array en orden inverso y comparamos el elemento actual y el anterior. Si se encuentra una coincidencia, imprimimos el índice y el elemento duplicado. Como esta es una array ordenada, será el último duplicado. Si no se encuentra dicho elemento, imprimiremos el mensaje correspondiente.
1- for i = n-1 to 0 if (arr[i] == arr[i-1]) Print current element and its index. Return 2- If no such element found print a message of no duplicate found.
C++
// To print last duplicate element and its // index in a sorted array #include <bits/stdc++.h> void dupLastIndex(int arr[], int n) { // if array is null or size is less // than equal to 0 return if (arr == NULL || n <= 0) return; // compare elements and return last // duplicate and its index for (int i = n - 1; i > 0; i--) { if (arr[i] == arr[i - 1]) { printf("Last index: %d\nLast " "duplicate item: %d\n", i, arr[i]); return; } } // If we reach here, then no duplicate // found. printf("no duplicate found"); } int main() { int arr[] = {1, 5, 5, 6, 6, 7, 9}; int n = sizeof(arr) / sizeof(int); dupLastIndex(arr, n); return 0; }
C
// C code To print last duplicate element and its // index in a sorted array #include <stdio.h> void dupLastIndex(int arr[], int n) { // if array is null or size is less // than equal to 0 return if (arr == NULL || n <= 0) return; // compare elements and return last // duplicate and its index for (int i = n - 1; i > 0; i--) { if (arr[i] == arr[i - 1]) { printf("Last index: %d\nLast " "duplicate item: %d\n", i, arr[i]); return; } } // If we reach here, then no duplicate // found. printf("no duplicate found"); } int main() { int arr[] = { 1, 5, 5, 6, 6, 7, 9 }; int n = sizeof(arr) / sizeof(int); dupLastIndex(arr, n); return 0; } // This code is contributed by muditj148.
Java
// Java code to print last duplicate element // and its index in a sorted array import java.io.*; class GFG { static void dupLastIndex(int arr[], int n) { // if array is null or size is less // than equal to 0 return if (arr == null || n <= 0) return; // compare elements and return last // duplicate and its index for (int i = n - 1; i > 0; i--) { if (arr[i] == arr[i - 1]) { System.out.println("Last index:" + i); System.out.println("Last duplicate item: " + arr[i]); return; } } // If we reach here, then no duplicate // found. System.out.print("no duplicate found"); } // Driver code public static void main (String[] args) { int arr[] = {1, 5, 5, 6, 6, 7, 9}; int n = arr.length; dupLastIndex(arr, n); } } // This code is contributed by vt_m
Python3
# Python3 code to print last duplicate # element and its index in a sorted array def dupLastIndex(arr, n): # if array is null or size is less # than equal to 0 return if (arr == None or n <= 0): return # compare elements and return last # duplicate and its index for i in range(n - 1, 0, -1): if (arr[i] == arr[i - 1]): print("Last index:", i, "\nLast", "duplicate item:",arr[i]) return # If we reach here, then no duplicate # found. print("no duplicate found") arr = [1, 5, 5, 6, 6, 7, 9] n = len(arr) dupLastIndex(arr, n) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# code to print last duplicate element // and its index in a sorted array using System; class GFG { static void dupLastIndex(int []arr, int n) { // if array is null or size is less // than equal to 0 return if (arr == null || n <= 0) return; // compare elements and return last // duplicate and its index for (int i = n - 1; i > 0; i--) { if (arr[i] == arr[i - 1]) { Console.WriteLine("Last index:" + i); Console.WriteLine("Last duplicate item: " + arr[i]); return; } } // If we reach here, then no duplicate // found. Console.WriteLine("no duplicate found"); } // Driver code public static void Main () { int []arr = {1, 5, 5, 6, 6, 7, 9}; int n = arr.Length; dupLastIndex(arr, n); } } // This code is contributed by vt_m.
PHP
<?php // PHP program to print last // duplicate element and its // index in a sorted array function dupLastIndex($arr, $n) { // if array is null or size is less // than equal to 0 return if ($arr == null or $n <= 0) return; // compare elements and return last // duplicate and its index for ( $i = $n - 1; $i > 0; $i--) { if ($arr[$i] == $arr[$i - 1]) { echo "Last index:", $i , "\n"; echo "Last duplicate item:", $arr[$i]; return; } } // If we reach here, then // no duplicate found. echo "no duplicate found"; } // Driver Code $arr = array(1, 5, 5, 6, 6, 7, 9); $n = count($arr); dupLastIndex($arr, $n); // This code is contributed by anuj_67. ?>
Javascript
<script> // JavaScript program to print last duplicate element // and its index in a sorted array function dupLastIndex(arr, n) { // if array is null or size is less // than equal to 0 return if (arr == null || n <= 0) return; // compare elements and return last // duplicate and its index for (let i = n - 1; i > 0; i--) { if (arr[i] == arr[i - 1]) { document.write("Last index:" + i + "<br/>"); document.write("Last duplicate item: " + arr[i] + "<br/>"); return; } } // If we reach here, then no duplicate // found. document.write("no duplicate found"); } // Driver code let arr = [1, 5, 5, 6, 6, 7, 9]; let n = arr.length; dupLastIndex(arr, n); </script>
Last index: 4 Last duplicate item: 6
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1), ya que no se utiliza espacio extra
Publicación traducida automáticamente
Artículo escrito por niteesh_Kr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA