Рубрики

Проверьте, являются ли элементы массива последовательными | Добавлен метод 3

Учитывая несортированный массив чисел, напишите функцию, которая возвращает истину, если массив состоит из последовательных чисел.

Примеры:
а) Если массив равен {5, 2, 3, 1, 4}, то функция должна вернуть значение true, поскольку массив имеет последовательные числа от 1 до 5.

б) Если массив равен {83, 78, 80, 81, 79, 82}, то функция должна возвращать true, поскольку массив имеет последовательные числа от 78 до 83.

c) Если массив равен {34, 23, 52, 12, 3}, то функция должна возвращать false, поскольку элементы не являются последовательными.

d) Если массив равен {7, 6, 5, 5, 3, 4}, то функция должна вернуть false, потому что 5 и 5 не являются последовательными.

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

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

Способ 2 (Использовать посещенный массив)
Идея состоит в том, чтобы проверить следующие два условия. Если следующие два условия верны, верните истину.
1) max — min + 1 = n, где max — максимальный элемент в массиве, min — минимальный элемент в массиве, а n — количество элементов в массиве.
2) Все элементы различны.

Чтобы проверить, все ли элементы различны, мы можем создать массив посещенных [] размером n. Мы можем отобразить i-й элемент входного массива arr [] в посещенный массив, используя arr [i] — min в качестве индекса для посещенного [].

C ++

#include<stdio.h>
#include<stdlib.h>

  
/ * Вспомогательные функции для получения минимума и максимума в массиве * /

int getMin(int arr[], int n);

int getMax(int arr[], int n);

  
/ * Функция проверяет, являются ли элементы массива последовательными

  Если элементы являются последовательными, то возвращает true, иначе возвращает

  ложный */

bool areConsecutive(int arr[], int n)

{

  if ( n <  1 )

    return false;

  

  / * 1) Получить минимальный элемент в массиве * /

  int min = getMin(arr, n);

  

  / * 2) Получить максимальный элемент в массиве * /

  int max = getMax(arr, n);

  

  / * 3) max - min + 1 равно n, тогда проверяем только все элементы * /

  if (max - min  + 1 == n)

  {

      / * Создать временный массив для хранения флага посещения всех элементов.

         Обратите внимание, что здесь используется calloc, так что все значения инициализируются

         как ложь * / 

      bool *visited = (bool *) calloc (n, sizeof(bool));

      int i;

      for (i = 0; i < n; i++)

      {

         / * Если мы увидим элемент снова, вернем false * /

         if ( visited[arr[i] - min] != false )

           return false;

  

         / * При первом посещении пометить элемент как посещенный * /

         visited[arr[i] - min] = true;

      }

  

      / * Если все элементы встречаются один раз, вернуть true * /

      return true;

  }

  

  return false; // if (max - min + 1! = n)

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /

int getMin(int arr[], int n)

{

  int min = arr[0];

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

   if (arr[i] < min)

     min = arr[i];

  return min;

}

  

int getMax(int arr[], int n)

{

  int max = arr[0];

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

   if (arr[i] > max)

     max = arr[i];

  return max;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[]= {5, 4, 2, 3, 1, 6};

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

    if(areConsecutive(arr, n) == true)

        printf(" Array elements are consecutive ");

    else

        printf(" Array elements are not consecutive ");

    getchar();

    return 0;

}

Джава

class AreConsecutive 

{

    / * Функция проверяет, являются ли элементы массива последовательными

       Если элементы являются последовательными, то возвращает true, иначе возвращает

       ложный */

    boolean areConsecutive(int arr[], int n) 

    {

        if (n < 1)

            return false;

  

        / * 1) Получить минимальный элемент в массиве * /

        int min = getMin(arr, n);

  

        / * 2) Получить максимальный элемент в массиве * /

        int max = getMax(arr, n);

  

        / * 3) max - min + 1 равно n, тогда проверяем только все элементы * /

        if (max - min + 1 == n) 

        {

            / * Создать временный массив для хранения флага посещения всех элементов.

               Обратите внимание, что здесь используется calloc, так что все значения инициализируются

               как ложь * /

            boolean visited[] = new boolean[n];

            int i;

            for (i = 0; i < n; i++) 

            {

                / * Если мы увидим элемент снова, вернем false * /

                if (visited[arr[i] - min] != false)

                    return false;

  

                / * При первом посещении пометить элемент как посещенный * /

                visited[arr[i] - min] = true;

            }

              

            / * Если все элементы встречаются один раз, вернуть true * /

            return true;

        }

        return false; // if (max - min + 1! = n)

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    int getMin(int arr[], int n) 

    {

        int min = arr[0];

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

        {

            if (arr[i] < min)

                min = arr[i];

        }

        return min;

    }

  

    int getMax(int arr[], int n) 

    {

        int max = arr[0];

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

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args) 

    {

        AreConsecutive consecutive = new AreConsecutive();

        int arr[] = {5, 4, 2, 3, 1, 6};

        int n = arr.length;

        if (consecutive.areConsecutive(arr, n) == true)

            System.out.println("Array elements are consecutive");

        else

            System.out.println("Array elements are not consecutive");

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Вспомогательные функции, чтобы получить минимум и
Максимум в массиве

  
# Функция проверяет наличие элементов массива
# являются последовательными. Если элементы являются последовательными,
# затем возвращает true, иначе возвращает false

def areConsecutive(arr, n):

  

    if ( n < 1 ):

        return False

      

    # 1) Получить элемент Minimum в массиве * /

    Min = min(arr)

      

    # 2) Получить элемент Maximum в массиве * /

    Max = max(arr)

      

    # 3) Макс - Мин + 1 равно n,

    # тогда проверяйте только все элементы * /

    if (Max - Min + 1 == n):

          

        # Создать временный массив для хранения посещенных

        # флаг всех элементов. Обратите внимание, что Calloc

        # используется здесь, чтобы все значения

        # инициализировано как ложное

        visited = [False for i in range(n)]

      

        for i in range(n):

              

            # Если мы увидим элемент снова,

            # затем верните false * /

            if (visited[arr[i] - Min] != False):

                return False

      

            # Если посетил в первый раз, то отметьте

            # элемент как посещенный * /

            visited[arr[i] - Min] = True

      

        # Если все элементы встречаются один раз,

        # затем верните true * /

        return True

      

    return False # if (Max - Min + 1! = n)

  
Код водителя

arr = [5, 4, 2, 3, 1, 6]

n = len(arr)

if(areConsecutive(arr, n) == True):

    print("Array elements are consecutive ")

else:

    print("Array elements are not consecutive ")

  
# Этот код предоставлен Мохит Кумар

C #

using System;

  

class GFG {

      

    / * Функция проверяет наличие элементов массива

    являются последовательными, если элементы являются последовательными,

    затем возвращает true, иначе возвращает false * /

    static bool areConsecutive(int []arr, int n) 

    {

        if (n < 1)

            return false;

  

        / * 1) Получить минимальный элемент в массиве * /

        int min = getMin(arr, n);

  

        / * 2) Получить максимальный элемент в массиве * /

        int max = getMax(arr, n);

  

        / * 3) max - min + 1 равно n, тогда

        только проверить все элементы * /

        if (max - min + 1 == n) 

        {

              

            / * Создать временный массив для хранения посещенных

            флаг всех элементов. Обратите внимание, что Calloc

            используется здесь, так что все значения

            инициализируется как false * /

            bool []visited = new bool[n];

            int i;

              

            for (i = 0; i < n; i++) 

            {

                  

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

                вернуть ложь * /

                if (visited[arr[i] - min] != false)

                    return false;

  

                / * При первом посещении отметьте

                элемент как посещенный * /

                visited[arr[i] - min] = true;

            }

              

            / * Если все элементы встречаются один раз, то

            вернуть истину * /

            return true;

        }

        return false; // if (max - min + 1! = n)

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    static int getMin(int []arr, int n) 

    {

        int min = arr[0];

          

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

        {

            if (arr[i] < min)

                min = arr[i];

        }

          

        return min;

    }

  

    static int getMax(int []arr, int n) 

    {

        int max = arr[0];

          

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

        {

            if (arr[i] > max)

                max = arr[i];

        }

          

        return max;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void Main() 

    {

        int []arr = {5, 4, 2, 3, 1, 6};

        int n = arr.Length;

          

        if (areConsecutive(arr, n) == true)

            Console.Write("Array elements are"

                              + " consecutive");

        else

            Console.Write("Array elements are"

                         + " not consecutive");

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Программа PHP для вышеуказанного подхода

  
// Функция проверяет наличие элементов массива
// являются последовательными Если элементы являются последовательными,
// затем возвращает true, иначе возвращает false

function areConsecutive($arr, $n

    if ( $n < 1 ) 

        return false; 

      

    // 1) Получить минимальный элемент в массиве

    $min = getMin($arr, $n); 

      

    // 2) Получить максимальный элемент в массиве

    $max = getMax($arr, $n); 

      

    // 3) $ max - $ min + 1 равно $ n,

    // тогда проверяем только все элементы

    if ($max - $min + 1 == $n

    

          

        // Создать временный массив для хранения

        // флаг посещения всех элементов.

        $visited = array(); 

        for ($i = 0; $i < $n; $i++) 

        

            $visited[$i] = false; 

        

        for ($i = 0; $i < $n; $i++) 

        

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

            // затем возвращаем false

            if ( $visited[$arr[$i] - $min] != false ) 

            return false; 

      

            // Если посетил в первый раз, то отметьте

            // элемент как посещенный

            $visited[$arr[$i] - $min] = true; 

        

      

        // Если все элементы встречаются один раз,

        // затем возвращаем true

        return true; 

    

      

    return false; // if ($ max - $ min + 1! = $ n)

  
// ПОЛЕЗНЫЕ ФУНКЦИИ

function getMin($arr, $n

    $min = $arr[0]; 

    for ($i = 1; $i < $n; $i++) 

        if ($arr[$i] < $min

            $min = $arr[$i]; 

    return $min

  

function getMax($arr, $n

    $max = $arr[0]; 

    for ($i = 1; $i < $n; $i++) 

        if ($arr[$i] > $max

            $max = $arr[$i]; 

    return $max

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

$arr = array(5, 4, 2, 3, 1, 6); 

$n = count($arr);

if(areConsecutive($arr, $n) == true) 

    echo "Array elements are consecutive "

else

    echo "Array elements are not consecutive "

      
// Этот код предоставлен rathbhupendra
?>

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

Способ 3 (пометить посещенные элементы массива как отрицательные)
Этот метод имеет O (n) временную сложность и O (1) дополнительное пространство, но он меняет исходный массив и работает, только если все числа положительны. Мы можем получить исходный массив, добавив дополнительный шаг. Это расширение метода 2, и оно имеет те же два шага.
1) max — min + 1 = n, где max — максимальный элемент в массиве, min — минимальный элемент в массиве, а n — количество элементов в массиве.
2) Все элементы различны.

В этом методе реализация шага 2 отличается от метода 2. Вместо создания нового массива мы модифицируем входной массив arr [], чтобы отслеживать посещенные элементы. Идея состоит в том, чтобы просмотреть массив и для каждого индекса i (где 0 ≤ i <n) сделать arr [arr [i] — min]] как отрицательное значение. Если мы снова видим отрицательное значение, то есть повторение.

C ++

#include<stdio.h>
#include<stdlib.h>

  
/ * Вспомогательные функции для получения минимума и максимума в массиве * /

int getMin(int arr[], int n);

int getMax(int arr[], int n);

  
/ * Функция проверяет, являются ли элементы массива последовательными

  Если элементы являются последовательными, то возвращает true, иначе возвращает

  ложный */

bool areConsecutive(int arr[], int n)

{

  

    if ( n <  1 )

        return false;

  

    / * 1) Получить минимальный элемент в массиве * /

    int min = getMin(arr, n);

  

    / * 2) Получить максимальный элемент в массиве * /

    int max = getMax(arr, n);

  

    / * 3) max - min + 1 равно n, тогда проверять только все элементы * /

    if (max - min  + 1 == n)

    {

        int i;

        for(i = 0; i < n; i++)

        {

            int j;

  

            if (arr[i] < 0)

                j = -arr[i] - min;

            else

                j = arr[i] - min;

  

            // если значение индекса j отрицательно, то

            // есть повторение

            if (arr[j] > 0)

                arr[j] = -arr[j];

            else

                return false;

        }

  

        / * Если мы не видим отрицательного значения, тогда все элементы

           различны * /

        return true;

    }

  

    return false; // if (max - min + 1! = n)

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /

int getMin(int arr[], int n)

{

    int min = arr[0];

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

        if (arr[i] < min)

            min = arr[i];

    return min;

}

  

int getMax(int arr[], int n)

{

    int max = arr[0];

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

        if (arr[i] > max)

            max = arr[i];

    return max;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[]= {1, 4, 5, 3, 2, 6};

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

    if(areConsecutive(arr, n) == true)

        printf(" Array elements are consecutive ");

    else

        printf(" Array elements are not consecutive ");

    getchar();

    return 0;

}

Джава

class AreConsecutive 

{

    / * Функция проверяет, являются ли элементы массива последовательными

       Если элементы являются последовательными, то возвращает true, иначе возвращает

       ложный */

    boolean areConsecutive(int arr[], int n) 

    {

        if (n < 1)

            return false;

  

        / * 1) Получить минимальный элемент в массиве * /

        int min = getMin(arr, n);

  

        / * 2) Получить максимальный элемент в массиве * /

        int max = getMax(arr, n);

  

        / * 3) max-min + 1 равно n, тогда проверяем только все элементы * /

        if (max - min + 1 == n) 

        {

            int i;

            for (i = 0; i < n; i++) 

            {

                int j;

  

                if (arr[i] < 0)

                    j = -arr[i] - min;

                else

                    j = arr[i] - min;

  

                // если значение индекса j отрицательно, то

                // есть повторение

                if (arr[j] > 0

                    arr[j] = -arr[j];

                else

                    return false;

            }

  

            / * Если мы не видим отрицательного значения, тогда все элементы

               различны * /

            return true;

        }

  

        return false; // if (max-min + 1! = n)

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    int getMin(int arr[], int n) 

    {

        int min = arr[0];

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

        {

            if (arr[i] < min)

                min = arr[i];

        }

        return min;

    }

  

    int getMax(int arr[], int n) 

    {

        int max = arr[0];

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

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args) 

    {

        AreConsecutive consecutive = new AreConsecutive();

        int arr[] = {5, 4, 2, 3, 1, 6};

        int n = arr.length;

        if (consecutive.areConsecutive(arr, n) == true)

            System.out.println("Array elements are consecutive");

        else

            System.out.println("Array elements are not consecutive");

    }

}

  
// Этот код предоставлен Mayank Jaiswal

Python 3

# Вспомогательные функции, чтобы получить минимум и
# максимум в массиве

  
# Функция проверяет, является ли массив
# элементы являются последовательными. Если элементы
# являются последовательными, затем возвращает true,
# else возвращает false

def areConsecutive(arr, n):

  

    if ( n < 1 ):

        return False

  

    # 1) Получить минимальный элемент в массиве

    min = getMin(arr, n)

  

    # 2) Получить максимальный элемент в массиве

    max = getMax(arr, n)

  

    # 3) max - min + 1 равно n

    # тогда проверяйте только все элементы

    if (max - min + 1 == n):

  

        for i in range(n):

  

            if (arr[i] < 0):

                j = -arr[i] - min

            else:

                j = arr[i] - min

  

            # если значение индекса j отрицательное

            # тогда есть повторение

            if (arr[j] > 0):

                arr[j] = -arr[j]

            else:

                return False

  

        # Если мы не видим отрицательное значение

        # тогда все элементы различны

        return True

  

    return False     # if (max - min + 1! = n)

  
# ПОЛЕЗНЫЕ ФУНКЦИИ

def getMin(arr, n):

      

    min = arr[0]

    for i in range(1, n):

        if (arr[i] < min):

            min = arr[i]

    return min

  

def getMax(arr, n):

    max = arr[0]

    for i in range(1, n):

        if (arr[i] > max):

            max = arr[i]

    return max

  
Код водителя

if __name__ == "__main__":

      

    arr = [1, 4, 5, 3, 2, 6]

    n = len(arr)

    if(areConsecutive(arr, n) == True):

        print(" Array elements are consecutive ")

    else:

        print(" Array elements are not consecutive ")

  
# Этот код предоставлен ita_c

C #

using System;

  

class GFG {

      

    / * Функция проверяет, является ли массив

    элементы являются последовательными, если элементы

    являются последовательными, а затем возвращает истину,

    else возвращает false * /

    static bool areConsecutive(int []arr, int n) 

    {

        if (n < 1)

            return false;

  

        / * 1) Получить минимальный элемент в

        массив * /

        int min = getMin(arr, n);

  

        / * 2) Получить максимальный элемент в

        массив * /

        int max = getMax(arr, n);

  

        / * 3) max-min + 1 равно n тогда

        только проверить все элементы * /

        if (max - min + 1 == n) 

        {

            int i;

            for (i = 0; i < n; i++) 

            {

                int j;

  

                if (arr[i] < 0)

                    j = -arr[i] - min;

                else

                    j = arr[i] - min;

  

                // если значение по индексу j

                // тогда отрицательно

                // есть повторение

                if (arr[j] > 0) 

                    arr[j] = -arr[j];

                else

                    return false;

            }

  

            / * Если мы не видим негатива

            значение тогда все элементы

            различны * /

            return true;

        }

  

        // if (max-min + 1! = n)

        return false

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    static int getMin(int []arr, int n) 

    {

        int min = arr[0];

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

        {

            if (arr[i] < min)

                min = arr[i];

        }

        return min;

    }

  

    static int getMax(int []arr, int n) 

    {

        int max = arr[0];

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

        {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

  

    / * Программа драйвера для тестирования выше

    функции * /

    public static void Main() 

    {

        int []arr = {5, 4, 2, 3, 1, 6};

        int n = arr.Length;

          

        if (areConsecutive(arr, n) == true)

            Console.Write("Array elements "

                      + "are consecutive");

        else

            Console.Write("Array elements "

                  + "are not consecutive");

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php

  
/ * Функция проверяет наличие элементов массива
являются последовательными, если элементы являются последовательными,
затем возвращает true, иначе возвращает false * /

function areConsecutive( $arr, $n)

{

  

    if ( $n < 1 )

        return false;

  

    / * 1) Получить минимальный элемент в массиве * /

    $min = getMin($arr, $n);

  

    / * 2) Получить максимальный элемент в массиве * /

    $max = getMax($arr, $n);

  

    / * 3) max - min + 1 равно n тогда

          только проверить все элементы * /

    if ($max - $min + 1 == $n)

    {

    $i;

        for($i = 0; $i < $n; $i++)

        {

            $j;

  

            if ($arr[$i] < 0)

                $j = -$arr[$i] - $min;

            else

                $j = $arr[$i] - $min;

  

            // если значение индекса j

            // отрицательно, то есть

            // повторение

            if ($arr[$j] > 0)

                $arr[$j] = -$arr[$j];

            else

                return false;

        }

  

        / * Если мы не видим отрицательного значения

        тогда все элементы различны * /

        return true;

    }

  

    return false; // if (max - min + 1! = n)

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /

function getMin( $arr, $n)

{

    $min = $arr[0];

    for ( $i = 1; $i < $n; $i++)

        if ($arr[$i] < $min)

            $min = $arr[$i];

    return $min;

}

  

function getMax( $arr, $n)

{

    $max = $arr[0];

    for ( $i = 1; $i < $n; $i++)

        if ($arr[$i] > $max)

            $max = $arr[$i];

    return $max;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

    $arr= array(1, 4, 5, 3, 2, 6);

    $n = count($arr);

    if(areConsecutive($arr, $n) == true)

        echo " Array elements are consecutive ";

    else

        echo " Array elements are not consecutive ";

  

  
// Этот код предоставлен anuj_67.
?>


Обратите внимание, что этот метод может не работать для отрицательных чисел. Например, он возвращает false для {2, 1, 0, -3, -1, -2}.

Сложность времени: O (n)
Дополнительное пространство: O (1)

Проверьте, являются ли элементы массива последовательными во времени O (n) и пространстве O (1) (обрабатывает как положительные, так и отрицательные числа)

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

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

Проверьте, являются ли элементы массива последовательными | Добавлен метод 3

0.00 (0%) 0 votes