Dada una array de N enteros positivos. La tarea es verificar si la array está ordenada en forma de onda.
Ejemplos :
Input: arr[] = {1, 2, 3, 4, 5}
Output: NO
Input: arr[] = {1, 5, 3, 7, 2, 8, 6}
Output: YES
Acercarse:
- Primero verifique el elemento en el índice 1, es decir, A[1] y observe el patrón.
- Si arr[1] es mayor que su elemento izquierdo y derecho, entonces este patrón será seguido por otros elementos.
- De lo contrario, si arr[1] es más pequeño que su elemento izquierdo y derecho, este patrón será seguido por otros elementos.
- Verifique el mismo patrón encontrado en los pasos anteriores. Si en algún momento se infringe esta regla, devuelve falso, de lo contrario, devuelve verdadero.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code to check if the array is wave array
#include <iostream>
using namespace std;
// Function to check if array is wave array
// arr : input array
// n : size of array
bool isWaveArray(int arr[], int n)
{
bool result = true;
/* Check the wave form
* If arr[1] is greater than left and right
* Same pattern will be followed by whole
* elements, else reverse pattern
* will be followed by array elements
*/
if (arr[1] > arr[0] && arr[1] > arr[2]) {
for (int i = 1; i < n - 1; i += 2) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
result = true;
}
else {
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0) {
if (arr[n - 1] <= arr[n - 2]) {
result = false;
}
}
}
else if (arr[1] < arr[0] && arr[1] < arr[2]) {
for (int i = 1; i < n - 1; i += 2) {
if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
result = true;
}
else {
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0) {
if (arr[n - 1] >= arr[n - 2]) {
result = false;
}
}
}
return result;
}
// Driver Code
int main()
{
// Array
int arr[] = { 1, 3, 2, 4 };
int n = sizeof(arr) / sizeof(int);
if (isWaveArray(arr, n)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
return 0;
}
Java
// Java code to check if the array is wave array
public class GFG {
// Function to check if array is wave array
// arr : input array
// n : size of array
static boolean isWaveArray(int arr[], int n)
{
boolean result = true;
/* Check the wave form
* If arr[1] is greater than left and right
* Same pattern will be followed by whole
* elements, else reverse pattern
* will be followed by array elements
*/
if (arr[1] > arr[0] && arr[1] > arr[2]) {
for (int i = 1; i < n - 1; i += 2) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
result = true;
}
else {
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0) {
if (arr[n - 1] <= arr[n - 2]) {
result = false;
}
}
}
else if (arr[1] < arr[0] && arr[1] < arr[2]) {
for (int i = 1; i < n - 1; i += 2) {
if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
result = true;
}
else {
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0) {
if (arr[n - 1] >= arr[n - 2]) {
result = false;
}
}
}
return result;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 3, 2, 4 };
int n = arr.length;
if (isWaveArray(arr, n)) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
// This Code is contributed by ANKITRAI1
}
Python 3
# Python 3 code to check if
# the array is wave array
# Function to check if
# array is wave array
# arr : input array
# n : size of array
def isWaveArray(arr , n):
result = True
# Check the wave form
# If arr[1] is greater than
# left and right. Same pattern
# will be followed by whole
# elements, else reverse pattern
# will be followed by array elements
if (arr[1] > arr[0] and arr[1] > arr[2]):
for i in range(1, n - 1, 2):
if (arr[i] > arr[i - 1] and
arr[i] > arr[i + 1]):
result = True
else :
result = False
break
# Check for last element
if (result == True and n % 2 == 0):
if (arr[n - 1] <= arr[n - 2]) :
result = False
elif (arr[1] < arr[0] and
arr[1] < arr[2]) :
for i in range(1, n - 1, 2) :
if (arr[i] < arr[i - 1] and
arr[i] < arr[i + 1]):
result = True
else :
result = False
break
# Check for last element
if (result == True and n % 2 == 0) :
if (arr[n - 1] >= arr[n - 2]) :
result = False
return result
# Driver Code
if __name__ == "__main__":
# Array
arr = [ 1, 3, 2, 4 ]
n = len(arr)
if (isWaveArray(arr, n)):
print("YES")
else:
print("NO")
# This code is contributed
# by ChitraNayal
C#
// C# code to check if the
// array is wave array
using System;
class GFG
{
// Function to check if array
// is wave array
// arr : input array
// n : size of array
static bool isWaveArray(int []arr, int n)
{
bool result = true;
/* Check the wave form
* If arr[1] is greater than left
* and right. Same pattern will be
* followed by whole elements, else
* reverse pattern will be followed
by array elements */
if (arr[1] > arr[0] && arr[1] > arr[2])
{
for (int i = 1; i < n - 1; i += 2)
{
if (arr[i] > arr[i - 1] &&
arr[i] > arr[i + 1])
{
result = true;
}
else
{
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0)
{
if (arr[n - 1] <= arr[n - 2])
{
result = false;
}
}
}
else if (arr[1] < arr[0] &&
arr[1] < arr[2])
{
for (int i = 1; i < n - 1; i += 2)
{
if (arr[i] < arr[i - 1] &&
arr[i] < arr[i + 1])
{
result = true;
}
else
{
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0)
{
if (arr[n - 1] >= arr[n - 2])
{
result = false;
}
}
}
return result;
}
// Driver code
public static void Main()
{
int []arr = { 1, 3, 2, 4 };
int n = arr.Length;
if (isWaveArray(arr, n))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
// This code is contributed
// by inder_verma
PHP
<?php
// PHP code to check if the array is wave array
// Function to check if array is wave array
// arr : input array
// n : size of array
function isWaveArray( $arr, $n)
{
$result = true;
/* Check the wave form
* If arr[1] is greater than left and right
* Same pattern will be followed by whole
* elements, else reverse pattern
* will be followed by array elements
*/
if ($arr[1] > $arr[0] &&
$arr[1] > $arr[2])
{
for ( $i = 1; $i < ($n - 1); $i += 2)
{
if ($arr[$i] > $arr[$i - 1] &&
$arr[$i] > $arr[$i + 1])
{
$result = true;
}
else
{
$result = false;
break;
}
}
// Check for last element
if ($result == true && $n % 2 == 0)
{
if ($arr[$n - 1] <= $arr[$n - 2])
{
$result = false;
}
}
}
else if ($arr[1] < $arr[0] &&
$arr[1] < $arr[2])
{
for ($i = 1; $i < $n - 1; $i += 2)
{
if ($arr[$i] < $arr[$i - 1] &&
$arr[$i] < $arr[$i + 1])
{
$result = true;
}
else
{
$result = false;
break;
}
}
// Check for last element
if ($result == true && $n % 2 == 0)
{
if ($arr[$n - 1] >= $arr[$n - 2])
{
$result = false;
}
}
}
return $result;
}
// Driver Code
// Array
$arr = array (1, 3, 2, 4 );
$n = sizeof($arr);
if (isWaveArray($arr, $n))
{
echo "YES";
}
else
{
echo "NO";
}
// This code is contributed by jit_t
?>
Javascript
<script>
// Javascript code to check if the array is wave array
// Function to check if array is wave array
// arr : input array
// n : size of array
function isWaveArray(arr, n)
{
let result = true;
/* Check the wave form
* If arr[1] is greater than left and right
* Same pattern will be followed by whole
* elements, else reverse pattern
* will be followed by array elements
*/
if (arr[1] > arr[0] && arr[1] > arr[2]) {
for (let i = 1; i < n - 1; i += 2) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
result = true;
}
else {
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0) {
if (arr[n - 1] <= arr[n - 2]) {
result = false;
}
}
}
else if (arr[1] < arr[0] && arr[1] < arr[2]) {
for (let i = 1; i < n - 1; i += 2) {
if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
result = true;
}
else {
result = false;
break;
}
}
// Check for last element
if (result == true && n % 2 == 0) {
if (arr[n - 1] >= arr[n - 2]) {
result = false;
}
}
}
return result;
}
// Array
let arr = [ 1, 3, 2, 4 ];
let n = arr.length;
if (isWaveArray(arr, n)) {
document.write("YES");
}
else {
document.write("NO");
}
// This code is contributed by divyeshrabadiya07.
</script>
Producción
YES
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)