Dado un número entero 
y dos conjuntos de números enteros H[] y C[] de tamaño donde H[] almacena la altura de edificios consecutivos y C[] almacena los códigos de color para aquellos edificios en los que están pintados.
La tarea es determinar cuántos colores son visibles a la vez desde la vista de la derecha, es decir, a la derecha del edificio más a la derecha.
Ejemplos:
Entrada: K = 5, H[] = {5, 4, 3, 2, 3}, C[] = {1, 2, 3, 4, 5}
Salida: 3
Entrada: K = 5, H[] = {1, 2, 3, 4, 5}, C[] = {3, 3, 3, 3, 3}
Salida: 1
Enfoque: al observar detenidamente, el problema anterior se puede simplificar para encontrar el número de edificios estrictamente crecientes desde la derecha con colores distintos.
- Almacene el último elemento de la array Height en la variable max .
- Ahora en una array Arr , en la posición correspondiente al elemento en el último almacén de la array de colores 1 .
- Ahora comience a recorrer la array Height de n-2 a 0 .
- Si obtenemos un elemento mayor que max , almacene esa variable en max y nuevamente en la array Arr , en la posición correspondiente al i-ésimo elemento en la array de color store 1 .
- Por último, cuente el número de 1 presentes en la array Arr . Da el número total de color visible desde el final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of
// colors visible
int colourVisible(int height[], int colour[], int K)
{
int arr[K + 1] = { 0 }, visible = 0;
int max = height[K - 1];
arr[colour[K - 1]] = 1;
for (int i = K - 2; i >= 0; i--) {
if (height[i] > max) {
max = height[i];
arr[colour[i]] = 1;
}
}
// Count the Number of 1's
for (int i = 1; i <= K; i++) {
if (arr[i] == 1)
visible++;
}
return visible;
}
// Driver code
int main()
{
int height[] = { 3, 5, 1, 2, 3 };
int colour[] = { 1, 2, 3, 4, 3 };
int K = sizeof(colour) / sizeof(colour[0]);
cout << colourVisible(height, colour, K);
return 0;
}
Java
//Java implementation of above approach
import java.io.*;
class GFG {
// Function to return the number of
// colors visible
static int colourVisible(int height[], int colour[], int K)
{
int arr[]=new int[K + 1] ;
int visible = 0;
int max = height[K - 1];
arr[colour[K - 1]] = 1;
for (int i = K - 2; i >= 0; i--) {
if (height[i] > max) {
max = height[i];
arr[colour[i]] = 1;
}
}
// Count the Number of 1's
for (int i = 1; i <= K; i++) {
if (arr[i] == 1)
visible++;
}
return visible;
}
// Driver code
public static void main (String[] args) {
int height[] = { 3, 5, 1, 2, 3 };
int colour[] = { 1, 2, 3, 4, 3 };
int K = colour.length;
System.out.println (colourVisible(height, colour, K));
}
}
Python3
# Python3 implementation of above approach # Function to return the number of # colors visible def colourVisible(height, colour, K): arr = [0 for i in range(K + 1)] visible = 0 max = height[K - 1] arr[colour[K - 1]] = 1 i = K - 2 while(i >= 0): if (height[i] > max): max = height[i] arr[colour[i]] = 1 i -= 1 # Count the Number of 1 complement for i in range(1, K + 1, 1): if (arr[i] == 1): visible += 1 return visible # Driver code if __name__ == '__main__': height = [3, 5, 1, 2, 3] colour = [1, 2, 3, 4, 3] K = len(colour) print(colourVisible(height, colour, K)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the number of
// colors visible
static int colourVisible(int []height,
int []colour, int K)
{
int []arr=new int[K + 1] ;
int visible = 0;
int max = height[K - 1];
arr[colour[K - 1]] = 1;
for (int i = K - 2; i >= 0; i--)
{
if (height[i] > max)
{
max = height[i];
arr[colour[i]] = 1;
}
}
// Count the Number of 1's
for (int i = 1; i <= K; i++)
{
if (arr[i] == 1)
visible++;
}
return visible;
}
// Driver code
static public void Main ()
{
int []height = { 3, 5, 1, 2, 3 };
int []colour = { 1, 2, 3, 4, 3 };
int K = colour.Length;
Console.WriteLine(colourVisible(height, colour, K));
}
}
// This code is contributed by Sach_Code
PHP
<?php
// PHP implementation of above approach
// Function to return the number of
// colors visible
function colourVisible($height, $colour, $K)
{
$arr = array_fill(0, $K + 1, 0);
$visible = 0;
$max = $height[$K - 1];
$arr[$colour[$K - 1]] = 1;
for ($i = $K - 2; $i >= 0; $i--)
{
if ($height[$i] > $max)
{
$max = $height[$i];
$arr[$colour[$i]] = 1;
}
}
// Count the Number of 1's
for ($i = 1; $i <= $K; $i++)
{
if ($arr[$i] == 1)
$visible++;
}
return $visible;
}
// Driver code
$height = array( 3, 5, 1, 2, 3 );
$colour = array( 1, 2, 3, 4, 3 );
$K = count($colour);
echo colourVisible($height, $colour, $K);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to return the number of
// colors visible
function colourVisible(height, colour, K)
{
var arr = Array(K+1).fill(0), visible = 0;
var max = height[K - 1];
arr[colour[K - 1]] = 1;
for (var i = K - 2; i >= 0; i--) {
if (height[i] > max) {
max = height[i];
arr[colour[i]] = 1;
}
}
// Count the Number of 1's
for (var i = 1; i <= K; i++) {
if (arr[i] == 1)
visible++;
}
return visible;
}
// Driver code
var height = [ 3, 5, 1, 2, 3 ];
var colour = [ 1, 2, 3, 4, 3 ];
var K = colour.length;
document.write( colourVisible(height, colour, K));
</script>
Producción:
2
Complejidad de tiempo: O(K), donde K es el tamaño de la array de colores
Espacio auxiliar: O(K), ya que se usa un tamaño adicional de K
Publicación traducida automáticamente
Artículo escrito por Naman_Garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA