Учитывая массив размера n , напишите программу, чтобы проверить, отсортирована ли она в порядке возрастания или нет. В массиве допускаются равные значения, и два последовательных равных значения считаются отсортированными.
Примеры:
Input : 20 21 45 89 89 90
Output : Yes
Input : 20 20 45 89 89 90
Output : Yes
Input : 20 20 78 98 99 97
Output : No
Рекурсивный подход:
Основная идея рекурсивного подхода:
1: If size of array is zero or one, return true.
2: Check last two elements of array, if they are
sorted, perform a recursive call with n-1
else, return false.
If all the elements will be found sorted, n will
eventually fall to one, satisfying Step 1.
Ниже приведена реализация с использованием рекурсии:
C ++
#include <bits/stdc++.h>
using namespace std;
int arraySortedOrNot(int arr[], int n)
{
if (n == 1 || n == 0)
return 1;
if (arr[n - 1] < arr[n - 2])
return 0;
return arraySortedOrNot(arr, n - 1);
}
int main()
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = sizeof(arr) / sizeof(arr[0]);
if (arraySortedOrNot(arr, n))
cout << "Yes\n";
else
cout << "No\n";
}
|
Джава
class CkeckSorted {
static int arraySortedOrNot(int arr[], int n)
{
if (n == 1 || n == 0)
return 1;
if (arr[n - 1] < arr[n - 2])
return 0;
return arraySortedOrNot(arr, n - 1);
}
public static void main(String[] args)
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = arr.length;
if (arraySortedOrNot(arr, n) != 0)
System.out.println("Yes");
else
System.out.println("No");
}
}
|
python3
def arraySortedOrNot(arr):
n = len(arr)
if n == 1 or n == 0:
return True
return arr[0]<= arr[1] and arraySortedOrNot(arr[1:])
arr = [20, 23, 23, 45, 78, 88]
if arraySortedOrNot(arr): print("Yes")
else: print("No")
|
C #
using System;
class CkeckSorted
{
static int arraySortedOrNot(int []arr, int n)
{
if (n == 1 || n == 0)
return 1;
if (arr[n - 1] < arr[n - 2])
return 0;
return arraySortedOrNot(arr, n - 1);
}
public static void Main(String[] args)
{
int []arr = { 20, 23, 23, 45, 78, 88 };
int n = arr.Length;
if (arraySortedOrNot(arr, n) != 0)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
|
Выход:
Yes
Сложность времени: O (n)
Вспомогательное пространство: O (n) для стека рекурсивных вызовов.
Итеративный подход: идея почти такая же. Преимущество итеративного подхода состоит в том, что он позволяет избежать использования пространства стека рекурсии и затрат на рекурсию.
Ниже приведена реализация с использованием итерации:
C ++
#include <bits/stdc++.h>
using namespace std;
bool arraySortedOrNot(int arr[], int n)
{
if (n == 0 || n == 1)
return true;
for (int i = 1; i < n; i++)
if (arr[i - 1] > arr[i])
return false;
return true;
}
int main()
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = sizeof(arr) / sizeof(arr[0]);
if (arraySortedOrNot(arr, n))
cout << "Yes\n";
else
cout << "No\n";
}
|
Джава
class GFG {
static boolean arraySortedOrNot(int arr[], int n)
{
if (n == 0 || n == 1)
return true;
for (int i = 1; i < n; i++)
if (arr[i - 1] > arr[i])
return false;
return true;
}
public static void main(String[] args)
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = arr.length;
if (arraySortedOrNot(arr, n))
System.out.print("Yes\n");
else
System.out.print("No\n");
}
}
|
python3
def arraySortedOrNot(arr, n):
if (n == 0 or n == 1):
return True
for i in range(1, n):
if (arr[i-1] > arr[i]):
return False
return True
arr = [20, 23, 23, 45, 78, 88]
n = len(arr)
if (arraySortedOrNot(arr, n)):
print("Yes")
else:
print("No")
|
C #
using System;
class GFG
{
static bool arraySortedOrNot(int []arr, int n)
{
if (n == 0 || n == 1)
return true;
for (int i = 1; i < n; i++)
if (arr[i - 1] > arr[i])
return false;
return true;
}
public static void Main(String[] args)
{
int []arr = { 20, 23, 23, 45, 78, 88 };
int n = arr.Length;
if (arraySortedOrNot(arr, n))
Console.Write("Yes\n");
else
Console.Write("No\n");
}
}
|
Выход:
Yes
Сложность времени: O (n)
Вспомогательное пространство: O (1)
Эта статья предоставлена Rohit Thapliyal . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Проверьте, отсортирован ли связанный список (итеративный и рекурсивный)
- Программа для усреднения массива (итеративная и рекурсивная)
- Проверьте, если обратный подмассив делает массив отсортированным
- Проверьте, отсортирован ли и повернут массив
- Проверьте, можно ли отсортировать массив с помощью одного обмена
- Проверьте, отсортирован ли данный массив попарно или нет
- Проверьте, можно ли разбить отсортированный массив на пары, сумма которых равна k
- Проверьте, можно ли отсортировать массив, используя перестановки только между заданными индексами
- Проверьте элемент большинства в отсортированном массиве
- Проверьте, не отсортирован ли данный массив (элементы находятся на расстоянии не более одной позиции)
- Проверьте, является ли данный массив отсортированным массивом или нет
- Программа для проверки, является ли массив массивом палиндрома или нет
- Программа для проверки, является ли массив битоническим или нет
- Программа для проверки, является ли массив палиндромом или не использует рекурсию
- Программа Python для проверки монотонности заданного массива
Программа для проверки, отсортирован массив или нет (итеративный и рекурсивный)
0.00 (0%) 0 votes