Рубрики

Замена элемента делает элементы массива последовательными

Дан массив положительных различных целых чисел. Нам нужно найти единственный элемент, замена которого любым другим значением делает элементы массива последовательными. Если невозможно сделать элементы массива последовательными, вернуть -1.

Примеры :

Input : arr[] = {45, 42, 46, 48, 47}
Output : 42
Explanation: We can replace 42 with either
44 or 48 to make array consecutive.

Input : arr[] = {5, 6, 7, 9, 10}
Output : 5 [OR 10]
Explanation: We can either replace 5 with 8
or 10 with 8 to make array elements 
consecutive.

Input : arr[] = {5, 6, 7, 9, 8}
Output : Array elements are already consecutive

Наивным подходом является проверка каждого элемента arr [], после замены которого производится последовательный или нет . Временная сложность для этого подхода O (n 2 )

Лучший подход основан на важном наблюдении, что ответом будет самый маленький или самый большой элемент, если ответ существует. Если ответ существует, то есть два случая.
1) Последовательность последовательных элементов начинается с минимального элемента массива, затем продолжается добавлением 1 к предыдущему.
2) Последовательность последовательных элементов начинается с максимального элемента массива, затем продолжается вычитанием 1 из предыдущего.

Мы делаем выше две серии и для каждой серии ищем элементы серии в массиве. Если для обеих серий число несоответствий больше 1, то ответа не существует. Если какая-либо серия найдена с одним несоответствием, то у нас есть ответ.

C ++

// CPP программа для поиска замены элемента
// который делает элементы массива последовательными
#include <bits/stdc++.h>

using namespace std;

  

int findElement(int arr[], int n)

{

    sort(arr, arr+n);

   

    // Создание серии, начиная с первого элемента

    // и добавляем 1 к каждому элементу.

    int mismatch_count1 = 0, res;

    int next_element = arr[n-1] - n + 1;

    for (int i=0; i<n-1; i++) {

       if (binary_search(arr, arr+n, next_element) == 0)

       {

          res = arr[0];  

          mismatch_count1++;

       }

        next_element++;

    }   

  

    // Если найдено только одно несоответствие.

    if (mismatch_count1 == 1)

        return res;

  

    // Если несоответствия не найдено, элементы

    // уже подряд.

    if (mismatch_count1 == 0)  

        return 0;

  

    // Создание серии, начиная с последнего элемента

    // и вычитая 1 для каждого элемента.

    int mismatch_count2 = 0;

    next_element = arr[0] + n - 1;

    for (int i=n-1; i>=1; i--) {

       if (binary_search(arr, arr+n, next_element) == 0)

       {

          res = arr[n-1];  

          mismatch_count2++;

       }      

       next_element--;

    }

          

    // Если найдено только одно несоответствие.

    if (mismatch_count2 == 1)

      return res;

        

    return -1;  

}

  
// Код драйвера

int main()

{

    int arr[] =  {7, 5, 12, 8} ;

    int n = sizeof(arr)/sizeof(arr[0]);

    int res = findElement(arr,n);

    if (res == -1)

      cout << "Answer does not exist";

    else if (res == 0)

      cout << "Elements are already consecutive";

    else

      cout << res;

    return 0;

}

Джава

// Java-программа для поиска элемента
// замена которого составляет
// элементы массива подряд.

import java.io.*;

import java.util.Arrays;

  

class GFG

{

    static int findElement(int []arr, 

                           int n)

    {

        Arrays.sort(arr);

      

        // Создание серии, начинающейся

        // из первого элемента и

        // добавляем 1 к каждому элементу.

        int mismatch_count1 = 0

                        res = 0;

        int next_element = arr[n - 1] - 

                               n + 1;

          

        for (int i = 0; i < n - 1; i++) 

        {

        if (Arrays.binarySearch(arr, 

                            next_element) < 0)

        {

            res = arr[0]; 

            mismatch_count1++;

        }

            next_element++;

        

      

        // Если найдено только одно несоответствие.

        if (mismatch_count1 == 1)

            return res;

      

        // Если несоответствия не найдено, элементы

        // уже подряд.

        if (mismatch_count1 == 0

            return 0;

      

        // Создание серии, начинающейся

        // из последнего элемента и

        // вычитаем 1 для каждого элемента.

        int mismatch_count2 = 0;

        next_element = arr[0] + n - 1;

          

        for (int i = n - 1; i >= 1; i--) 

        {

        if (Arrays.binarySearch(arr, 

                            next_element) < 0)

        {

            res = arr[n - 1]; 

            mismatch_count2++;

        }     

        next_element--;

        }

              

        // Если найдено только одно несоответствие.

        if (mismatch_count2 == 1)

        return res;

              

        return -1

    }

      

    // Код драйвера

    public static void main(String args[])

    {

        int []arr = new int[]{7, 5, 12, 8} ;

        int n = arr.length;

        int res = findElement(arr,n);

        if (res == -1)

        System.out.print("Answer does not exist");

        else if (res == 0)

        System.out.print("Elements are "

                         "already consecutive");

        else

        System.out.print(res);

    }

}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

C #

// C # программа для поиска элемента
// замена которого составляет
// элементы массива подряд.

using System;

using System.Linq;

using System.Collections.Generic;

  

class GFG

{

    static int findElement(int []arr, 

                           int n)

    {

        Array.Sort(arr);

      

        // Создание серии, начинающейся

        // из первого элемента и

        // добавляем 1 к каждому элементу.

        int mismatch_count1 = 0, res = 0;

        int next_element = arr[n - 1] - n + 1;

          

        for (int i = 0; i < n - 1; i++) 

        {

        if (Array.BinarySearch(arr, 

                               next_element) < 0)

        {

            res = arr[0]; 

            mismatch_count1++;

        }

            next_element++;

        

      

        // Если найдено только одно несоответствие.

        if (mismatch_count1 == 1)

            return res;

      

        // Если несоответствия не найдено, элементы

        // уже подряд.

        if (mismatch_count1 == 0) 

            return 0;

      

        // Создание серии, начинающейся

        // из последнего элемента и

        // вычитаем 1 для каждого элемента.

        int mismatch_count2 = 0;

        next_element = arr[0] + n - 1;

          

        for (int i = n - 1; i >= 1; i--) 

        {

        if (Array.BinarySearch(arr, 

                               next_element) < 0)

        {

            res = arr[n - 1]; 

            mismatch_count2++;

        }     

        next_element--;

        }

              

        // Если найдено только одно несоответствие.

        if (mismatch_count2 == 1)

        return res;

              

        return -1; 

    }

      

    // Код драйвера

    static void Main()

    {

        int []arr = new int[]{7, 5, 12, 8} ;

        int n = arr.Length;

        int res = findElement(arr,n);

        if (res == -1)

        Console.Write("Answer does not exist");

        else if (res == 0)

        Console.Write("Elements are "

                      "already consecutive");

        else

        Console.Write(res);

    }

}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

Выход :

12

Сложность времени: O (n Log n)

Рекомендуемые посты:

Замена элемента делает элементы массива последовательными

0.00 (0%) 0 votes