Dadas dos arrays desordenadas arr1[] y arr2[]. Pueden contener duplicados. Para cada elemento en arr1[] cuente los elementos menores o iguales que él en la array arr2[].
Fuente: experiencia de entrevista de Amazon | Juego 354 (para SDE-2)
Ejemplos:
Input : arr1[] = [1, 2, 3, 4, 7, 9]
arr2[] = [0, 1, 2, 1, 1, 4]
Output : [4, 5, 5, 6, 6, 6]
So the number of elements less than or equal to
1 is 4, 2 is 5, 3 is 5, 4 is 6, 7 is 6 and 9 is 6.
Input : arr1[] = [5, 10, 2, 6, 1, 8, 6, 12]
arr2[] = [6, 5, 11, 4, 2, 3, 7]
Output : [4, 6, 1, 5, 0, 6, 5, 7]
So the number of elements less than or equal to
5 is 4, 10 is 6, 2 is 1, 6 is 5, 1 is 0, 8 is 6,
6 is 5 and 12 is 7
Enfoque ingenuo:
Enfoque: la idea es utilizar dos bucles, el bucle exterior para los elementos de la array arr1[] y un bucle interior para los elementos de la array arr2[] . Luego, para cada elemento de arr1[] , cuente los elementos menores o iguales en arr2[] .
Algoritmo:
- Recorra los elementos de la primera array de principio a fin.
- Para cada elemento en la primera array.
- Recorra los elementos de la segunda array y encuentre la cantidad de elementos que son menores o iguales que el elemento de la primera array.
- Imprime el conteo para cada índice.
Implementación:
C++
// C++ code for the above algorithm
#include <bits/stdc++.h>
using namespace std;
// Function to count for each
// element in 1st array,
// elements less than or equal
// to it in 2nd array
void countEleLessThanOrEqual(int arr1[], int arr2[],
int m, int n)
{
// Run two loops to count
// First loop to traverse the first array
// Second loop to traverse the second array
for (int i = 0; i < m; i++) {
int count = 0;
// Traverse through second array
for (int j = 0; j < n; j++)
if (arr2[j] <= arr1[i])
count++;
cout << count << " ";
}
}
// Driver program to test above
int main()
{
int arr1[] = { 1, 2, 3, 4, 7, 9 };
int arr2[] = { 0, 1, 2, 1, 1, 4 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
countEleLessThanOrEqual(arr1, arr2, m, n);
return 0;
}
Java
import java.util.Arrays;
class GFG {
// function to count for each
// element in 1st array,
// elements less than or equal
// to it in 2nd array
static int countEleLessThanOrEqual(
int arr1[], int arr2[],
int m, int n)
{
// Run two loops to count
// First loop to traverse the first array
// Second loop to traverse the second array
for (int i = 0; i < m; i++) {
int count = 0;
// Traverse through second array
for (int j = 0; j < n; j++)
if (arr2[j] <= arr1[i])
count++;
System.out.print(count + " ");
}
return m;
}
// Driver method
public static void main(String[] args)
{
int arr1[] = { 1, 2, 3, 4, 7, 9 };
int arr2[] = { 0, 1, 2, 1, 1, 4 };
countEleLessThanOrEqual(
arr1, arr2, arr1.length, arr2.length);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 code for the above algorithm # function to count for each element in 1st array, # elements less than or equal to it in 2nd array def countEleLessThanOrEqual(arr1, arr2, m, n): # Run two loops to count # First loop to traverse the first array # Second loop to traverse the second array for i in range(m): count = 0 # Traverse through second array for j in range(n): if (arr2[j] <= arr1[i]): count+= 1 print(count, end =" ") # Driver program to test above arr1 = [1, 2, 3, 4, 7, 9] arr2 = [0, 1, 2, 1, 1, 4] m = len(arr1) n = len(arr2) countEleLessThanOrEqual(arr1, arr2, m, n) # This code is contributed by shubhamsingh10
C#
// C# implementation of For each element
using System;
class GFG {
// function to count for each element in 1st array,
// elements less than or equal to it in 2nd array
static void countEleLessThanOrEqual(
int[] arr1, int[] arr2,
int m, int n)
{
// Run two loops to count
// First loop to traverse the first array
// Second loop to traverse the second array
for (int i = 0; i < m; i++) {
int count = 0;
// Traverse through second array
for (int j = 0; j < n; j++)
if (arr2[j] <= arr1[i])
count++;
Console.Write((count) + " ");
}
}
// Driver method
public static void Main()
{
int[] arr1 = { 1, 2, 3, 4, 7, 9 };
int[] arr2 = { 0, 1, 2, 1, 1, 4 };
countEleLessThanOrEqual(arr1,
arr2, arr1.Length, arr2.Length);
}
}
// This code is contributed by mohit kumar 29.
Javascript
<script>
// JavaScript code for the above algorithm
// Function to count for each
// element in 1st array,
// elements less than or equal
// to it in 2nd array
function countEleLessThanOrEqual(arr1, arr2, m, n)
{
// Run two loops to count
// First loop to traverse the first array
// Second loop to traverse the second array
for (let i = 0; i < m; i++) {
let count = 0;
// Traverse through second array
for (let j = 0; j < n; j++)
if (arr2[j] <= arr1[i])
count++;
document.write(count + " ");
}
}
// Driver program to test above
let arr1 = [ 1, 2, 3, 4, 7, 9 ];
let arr2 = [ 0, 1, 2, 1, 1, 4 ];
let m = arr1.length;
let n = arr2.length;
countEleLessThanOrEqual(arr1, arr2, m, n);
// This code is contributed by Surbhi Tyagi.
</script>
Producción
4 5 5 6 6 6
Análisis de Complejidad:
- Complejidad temporal: O(m * n).
Considerando que arr1[] y arr2[] son de tamaño m y n respectivamente. - Complejidad espacial: O(1).
Como no se requiere espacio adicional
Solución eficiente:
Enfoque: ordenar los elementos de la segunda array, es decir, array arr2[] . Luego realice una búsqueda binaria modificada en la array arr2[] . Para cada elemento x de la array arr1[] , busque el último índice del elemento más grande menor o igual que x en la array ordenada arr2[] . El índice del elemento más grande dará la cuenta de elementos.
Algoritmo:
- Ordena la segunda array.
- Recorra los elementos de la primera array de principio a fin.
- Para cada elemento en la primera array.
- Realice una búsqueda binaria en la segunda array y encuentre el índice del elemento más grande menor o igual que el elemento de la primera array.
- El índice del elemento más grande dará la cuenta de elementos. Imprime el conteo para cada índice.
C++
// C++ implementation of For each element in 1st
// array count elements less than or equal to it
// in 2nd array
#include <bits/stdc++.h>
using namespace std;
// function returns the index of largest element
// smaller than equal to 'x' in 'arr'. For duplicates
// it returns the last index of occurrence of required
// element. If no such element exits then it returns -1.
int binary_search(int arr[], int l, int h, int x)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or equal to arr[mid],
// then search in arr[mid+1...h]
if (arr[mid] <= x)
l = mid + 1;
// else search in arr[l...mid-1]
else
h = mid - 1;
}
// required index
return h;
}
// function to count for each element in 1st array,
// elements less than or equal to it in 2nd array
void countEleLessThanOrEqual(
int arr1[], int arr2[],
int m, int n)
{
// sort the 2nd array
sort(arr2, arr2 + n);
// for each element of 1st array
for (int i = 0; i < m; i++) {
// last index of largest element
// smaller than or equal to x
int index = binary_search(
arr2, 0, n - 1, arr1[i]);
// required count for the element arr1[i]
cout << (index + 1) << " ";
}
}
// Driver program to test above
int main()
{
int arr1[] = { 1, 2, 3, 4, 7, 9 };
int arr2[] = { 0, 1, 2, 1, 1, 4 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
countEleLessThanOrEqual(arr1, arr2, m, n);
return 0;
}
Java
// Java implementation of For
// each element in 1st
// array count elements less
// than or equal to it
// in 2nd array
import java.util.Arrays;
class GFG {
// method returns the index
// of largest element
// smaller than equal to 'x'
// in 'arr'. For duplicates
// it returns the last index
// of occurrence of required
// element. If no such element
// exits then it returns -1.
static int binary_search(
int arr[], int l,
int h, int x)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or equal
// to arr[mid], then search in
// arr[mid+1...h]
if (arr[mid] <= x)
l = mid + 1;
// else search in arr[l...mid-1]
else
h = mid - 1;
}
// Required index
return h;
}
// Method to count for each
// element in 1st array,
// elements less than or equal
// to it in 2nd array
static void countEleLessThanOrEqual(
int arr1[], int arr2[],
int m, int n)
{
// Sort the 2nd array
Arrays.sort(arr2);
// for each element of 1st array
for (int i = 0; i < m; i++) {
// Last index of largest element
// smaller than or equal to x
int index = binary_search(
arr2, 0, n - 1, arr1[i]);
// Required count for the element arr1[i]
System.out.print((index + 1) + " ");
}
}
// Driver method
public static void main(String[] args)
{
int arr1[] = { 1, 2, 3, 4, 7, 9 };
int arr2[] = { 0, 1, 2, 1, 1, 4 };
countEleLessThanOrEqual(
arr1, arr2, arr1.length,
arr2.length);
}
}
Python3
# python implementation of For each element in 1st # array count elements less than or equal to it # in 2nd array # function returns the index of largest element # smaller than equal to 'x' in 'arr'. For duplicates # it returns the last index of occurrence of required # element. If no such element exits then it returns -1 def bin_search(arr, n, x): l = 0 h = n - 1 while(l <= h): mid = int((l + h) // 2) # if 'x' is greater than or equal to arr[mid], # then search in arr[mid + 1...h] if(arr[mid] <= x): l = mid + 1; else: # else search in arr[l...mid-1] h = mid - 1 # required index return h # function to count for each element in 1st array, # elements less than or equal to it in 2nd array def countElements(arr1, arr2, m, n): # sort the 2nd array arr2.sort() # for each element in first array for i in range(m): # last index of largest element # smaller than or equal to x index = bin_search(arr2, n, arr1[i]) # required count for the element arr1[i] print(index + 1,end=" ") # driver program to test above function arr1 = [1, 2, 3, 4, 7, 9] arr2 = [0, 1, 2, 1, 1, 4] m = len(arr1) n = len(arr2) countElements(arr1, arr2, m, n) # This code is contributed by Aditi Sharma
C#
// C# implementation of For each element
// in 1st array count elements less than
// or equal to it in 2nd array
using System;
public class GFG {
// method returns the index of
// largest element smaller than
// equal to 'x' in 'arr'. For
// duplicates it returns the last
// index of occurrence of required
// element. If no such element
// exits then it returns -1.
static int binary_search(int[] arr,
int l, int h, int x)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or
// equal to arr[mid], then
// search in arr[mid+1...h]
if (arr[mid] <= x)
l = mid + 1;
// else search in
// arr[l...mid-1]
else
h = mid - 1;
}
// required index
return h;
}
// method to count for each element
// in 1st array, elements less than
// or equal to it in 2nd array
static void countEleLessThanOrEqual(
int[] arr1, int[] arr2,
int m, int n)
{
// sort the 2nd array
Array.Sort(arr2);
// for each element of 1st array
for (int i = 0; i < m; i++) {
// last index of largest
// element smaller than or
// equal to x
int index = binary_search(
arr2, 0, n - 1, arr1[i]);
// required count for the
// element arr1[i]
Console.Write((index + 1) + " ");
}
}
// Driver method
public static void Main()
{
int[] arr1 = { 1, 2, 3, 4, 7, 9 };
int[] arr2 = { 0, 1, 2, 1, 1, 4 };
countEleLessThanOrEqual(arr1,
arr2, arr1.Length, arr2.Length);
}
}
// This code is contributed by Sam007.
PHP
<?php
// php implementation of For each element
// in 1st array count elements less than
// or equal to it in 2nd array
// function returns the index of largest
// element smaller than equal to 'x' in
// 'arr'. For duplicates it returns the
// last index of occurrence of required
// element. If no such element exits then
// it returns -1.
function binary_search($arr, $l, $h, $x)
{
while ($l <= $h)
{
$mid = (floor($l+$h) / 2);
// if 'x' is greater than or
// equal to arr[mid], then
// search in arr[mid+1...h]
if ($arr[$mid] <= $x)
$l = $mid + 1;
// else search in arr[l...mid-1]
else
$h = $mid - 1;
}
// required index
return $h;
}
// function to count for each element
// in 1st array, elements less than or
// equal to it in 2nd array
function countEleLessThanOrEqual($arr1,
$arr2, $m, $n)
{
// sort the 2nd array
sort($arr2); sort($arr2, $n);
// for each element of 1st array
for ($i = 0; $i < $m; $i++)
{
// last index of largest element
// smaller than or equal to x
$index = binary_search($arr2, 0,
$n-1, $arr1[$i]);
// required count for the
// element arr1[i]
echo ($index+1), " ";
}
}
// Driver program to test above
$arr1 = array(1, 2, 3, 4, 7, 9);
$arr2 = array(0, 1, 2, 1, 1, 4);
$m = sizeof($arr1) / sizeof($arr1[0]);
$n = sizeof($arr2) / sizeof($arr2[0]);
countEleLessThanOrEqual($arr1, $arr2, $m, $n);
//This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript implementation of For
// each element in 1st
// array count elements less
// than or equal to it
// in 2nd array
// method returns the index
// of largest element
// smaller than equal to 'x'
// in 'arr'. For duplicates
// it returns the last index
// of occurrence of required
// element. If no such element
// exits then it returns -1.
function binary_search(arr,l,h,x)
{
while (l <= h) {
let mid = Math.floor((l + h) / 2);
// if 'x' is greater than or equal
// to arr[mid], then search in
// arr[mid+1...h]
if (arr[mid] <= x)
l = mid + 1;
// else search in arr[l...mid-1]
else
h = mid - 1;
}
// Required index
return h;
}
// Method to count for each
// element in 1st array,
// elements less than or equal
// to it in 2nd array
function countEleLessThanOrEqual(arr1,arr2,m,n)
{
// Sort the 2nd array
arr2.sort(function(a,b){return a-b;});
// for each element of 1st array
for (let i = 0; i < m; i++) {
// Last index of largest element
// smaller than or equal to x
let index = binary_search(
arr2, 0, n - 1, arr1[i]);
// Required count for the element arr1[i]
document.write((index + 1) + " ");
}
}
// Driver method
let arr1=[1, 2, 3, 4, 7, 9 ];
let arr2=[0, 1, 2, 1, 1, 4];
countEleLessThanOrEqual(
arr1, arr2, arr1.length,
arr2.length);
// This code is contributed by patel2127
</script>
Producción
4 5 5 6 6 6
Análisis de Complejidad:
- Complejidad temporal: O(mlogn + nlogn).
Considerando arr1[] y arr2[] de tamaños m y n respectivamente. - Complejidad espacial: O(1).
Como no se requiere espacio adicional
Otra forma de resolver el problema es ordenar la segunda array y usar la función incorporada upper_bound() para cada valor de la primera array.
Implementación:
C++
// C++ implementation of For each element in 1st
// array count elements less than or equal to it
// in 2nd array
#include <bits/stdc++.h>
using namespace std;
// function to count for each element in 1st array,
// elements less than or equal to it in 2nd array
void countEleLessThanOrEqual(int arr1[], int arr2[], int m, int n)
{
// sort the 2nd array
sort(arr2, arr2 + n);
// for each element of 1st array
for (int i = 0; i < m; i++) {
int x = upper_bound(arr2, arr2 + n, arr1[i]) - arr2;
cout << x << " ";
}
}
// Driver program to test above
int main()
{
int arr1[] = { 1, 2, 3, 4, 7, 9 };
int arr2[] = { 0, 1, 2, 1, 1, 4 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
countEleLessThanOrEqual(arr1, arr2, m, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// JAVA implementation of For each element in 1st
// array count elements less than or equal to it
// in 2nd array
import java.util.*;
class GFG
{
public static int upper_bound(int arr[], int key)
{
int upperBound = 0;
while (upperBound < arr.length)
{
// If current value is lesser than or equal to
// key
if (arr[upperBound] <= key)
upperBound++;
// This value is just greater than key
else {
return upperBound;
}
}
return upperBound;
}
// function to count for each element in 1st array,
// elements less than or equal to it in 2nd array
public static void countEleLessThanOrEqual(int arr1[],
int arr2[],
int m, int n)
{
// sort the 2nd array
Arrays.sort(arr2);
// for each element of 1st array
for (int i = 0; i < m; i++) {
int x = upper_bound(arr2, arr1[i]);
System.out.print(x + " ");
}
}
// Driver program to test above
public static void main(String[] args)
{
int arr1[] = { 1, 2, 3, 4, 7, 9 };
int arr2[] = { 0, 1, 2, 1, 1, 4 };
int m = arr1.length;
int n = arr2.length;
countEleLessThanOrEqual(arr1, arr2, m, n);
}
}
// This code is contributed by Taranpreet
Producción
4 5 5 6 6 6
Complejidad de tiempo: O (n logn + m log n), donde m y n representan el tamaño de las dos arrays dadas.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Otro enfoque: también podemos usar dos punteros para encontrar nuestra solución. primero, ordene ambas arrays. después de ordenar, coloque el puntero i para arr1 y el puntero j para arr2 al principio. atravesaremos los elementos de arr1 usando el puntero i y dentro de este bucle, pasaremos por cada elemento de arr2 con el puntero j . dondequiera que arr2[j] <= arr1[i] aumentaremos j . si la condición falla, imprima j .
Nota: – esto dará respuesta de manera ordenada
C++
// C++ implementation of For each element in 1st
// array count elements less than or equal to it
// in 2nd array
#include <bits/stdc++.h>
using namespace std;
void countEleLessThanOrEqual(int arr1[], int arr2[], int m, int n)
{
// sorting both the arrays
sort(arr1, arr1 + m);
sort(arr2, arr2 + n);
// pointer for arr2
int j = 0;
// traversing each element of 1st array
for (int i = 0; i < m; i++)
{
// checking the condition for each element
while (j < n && arr2[j] <= arr1[i])
j++;
cout << j << " ";
}
}
// Driver program to test above
int main()
{
int arr1[] = {1, 2, 3, 4, 7, 9};
int arr2[] = {0, 1, 2, 1, 1, 4};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
countEleLessThanOrEqual(arr1, arr2, m, n);
return 0;
}
// This code is contributed by Naveen Shah
Producción
4 5 5 6 6 6
Complejidad de tiempo: O(nlogn + mlogm)
Espacio auxiliar: O(1)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA