Último elemento duplicado en una array ordenada

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *