Una array escalonada es una array de enteros donde cada elemento tiene una diferencia de como máximo k con su vecino. Dada una clave x, necesitamos encontrar el valor de índice de x si existen elementos múltiples para devolver la primera aparición de la clave.
Ejemplos:
Input : arr[] = {4, 5, 6, 7, 6}
k = 1
x = 6
Output : 2
The first index of 6 is 2.
Input : arr[] = {20, 40, 50, 70, 70, 60}
k = 20
x = 60
Output : 5
The index of 60 is 5
Este problema es principalmente una extensión de Buscar un elemento en una array donde la diferencia entre elementos adyacentes es 1 .
Un enfoque simple es recorrer la array dada uno por uno y comparar cada elemento con el elemento ‘x’ dado. Si coincide, devuelve index.
La solución anterior se puede optimizar utilizando el hecho de que la diferencia entre todos los elementos adyacentes es como máximo k. La idea es comenzar a comparar desde el elemento más a la izquierda y encontrar la diferencia entre el elemento de array actual y x. Sea esta diferencia ‘diff’. De la propiedad dada de la array, siempre sabemos que x debe estar al menos a ‘diff/k’, así que en lugar de buscar uno por uno, saltamos ‘diff/k’.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to search an element in an array
// where difference between adjacent elements is atmost k
#include<bits/stdc++.h>
using namespace std;
// x is the element to be searched in arr[0..n-1]
// such that all elements differ by at-most k.
int search(int arr[], int n, int x, int k)
{
// Traverse the given array starting from
// leftmost element
int i = 0;
while (i < n)
{
// If x is found at index i
if (arr[i] == x)
return i;
// Jump the difference between current
// array element and x divided by k
// We use max here to make sure that i
// moves at-least one step ahead.
i = i + max(1, abs(arr[i]-x)/k);
}
cout << "number is not present!";
return -1;
}
// Driver program to test above function
int main()
{
int arr[] = {2, 4, 5, 7, 7, 6};
int x = 6;
int k = 2;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Element " << x << " is present at index "
<< search(arr, n, x, k);
return 0;
}
Java
// Java program to search an element in
// an array where difference between adjacent elements is atmost k
import java.io.*;
class GFG {
// x is the element to be searched
// in arr[0..n-1] such that all
// elements differ by at-most k.
static int search(int arr[], int n,
int x, int k)
{
// Traverse the given array starting
// from leftmost element
int i = 0;
while (i < n) {
// If x is found at index i
if (arr[i] == x)
return i;
// Jump the difference between
// current array element and x
// divided by k We use max here
// to make sure that i moves
// at-least one step ahead.
i = i + Math.max(1, Math.abs(arr[i]
- x) / k);
}
System.out.println("number is " +
"not present!");
return -1;
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 2, 4, 5, 7, 7, 6 };
int x = 6;
int k = 2;
int n = arr.length;
System.out.println("Element " + x +
" is present at index "
+ search(arr, n, x, k));
}
}
// This code is contributed by vt_m
Python3
# Python 3 program to search an element in an array
# where difference between adjacent elements is atmost k
# x is the element to be searched in arr[0..n-1]
# such that all elements differ by at-most k.
def search(arr, n, x, k):
# Traverse the given array starting from
# leftmost element
i = 0
while (i < n):
# If x is found at index i
if (arr[i] == x):
return i
# Jump the difference between current
# array element and x divided by k
# We use max here to make sure that i
# moves at-least one step ahead.
i = i + max(1, int(abs(arr[i] - x) / k))
print("number is not present!")
return -1
# Driver program to test above function
arr = [2, 4, 5, 7, 7, 6]
x = 6
k = 2
n = len(arr)
print("Element", x, "is present at index",search(arr, n, x, k))
# This code is contributed
# by Smitha Dinesh Semwal
C#
// C# program to search an element in
// an array where difference between
//adjacent elements is atmost k
class GFG {
// x is the element to be searched
// in arr[0..n-1] such that all
// elements differ by at-most k.
static int search(int []arr, int n,
int x, int k)
{
// Traverse the given array starting
// from leftmost element
int i = 0;
while (i < n)
{
// If x is found at index i
if (arr[i] == x)
return i;
// Jump the difference between
// current array element and x
// divided by k We use max here
// to make sure that i moves
// at-least one step ahead.
i = i + Math.Max(1, Math.Abs(arr[i]
- x) / k);
}
Console.Write("number is " +
"not present!");
return -1;
}
// Driver Code
public static void Main()
{
int []arr = { 2, 4, 5, 7, 7, 6 };
int x = 6;
int k = 2;
int n = arr.Length;
Console.Write("Element " + x +
" is present at index " +
search(arr, n, x, k));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to search an
// element in an array
//where difference between
//adjacent elements is atmost k
// x is the element to be
// searched in arr[0..n-1]
// such that all elements
// differ by at-most k.
function search($arr, $n, $x, $k)
{
// Traverse the given array
// starting from leftmost element
$i = 0;
while ($i < $n)
{
// If x is found at index i
if ($arr[$i] == $x)
return $i;
// Jump the difference between current
// array element and x divided by k
// We use max here to make sure that i
// moves at-least one step ahead.
$i = $i + max(1, abs($arr[$i] - $x) / $k);
}
echo "number is not present!";
return -1;
}
// Driver Code
{
$arr = array(2, 4, 5, 7, 7, 6);
$x = 6;
$k = 2;
$n = sizeof($arr)/sizeof($arr[0]);
echo "Element $x is present".
"at index ",
search($arr, $n, $x, $k);
return 0;
}
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript program to search an element in an array
// where difference between adjacent elements is atmost k
// x is the element to be searched in arr[0..n-1]
// such that all elements differ by at-most k.
function search(arr, n, x, k)
{
// Traverse the given array starting from
// leftmost element
var i = 0;
while (i < n)
{
// If x is found at index i
if (arr[i] == x)
return i;
// Jump the difference between current
// array element and x divided by k
// We use max here to make sure that i
// moves at-least one step ahead.
i = i + Math.max(1, Math.abs(arr[i]-x)/k);
}
document.write( "number is not present!");
return -1;
}
// Driver program to test above function
var arr = [2, 4, 5, 7, 7, 6];
var x = 6;
var k = 2;
var n = arr.length;
document.write( "Element " + x + " is present at index "
+ search(arr, n, x, k));
</script>
Producción:
Element 6 is present at index 5
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA