Dada una array A de N enteros. Una anomalía es un número para el cual la diferencia absoluta entre él y todos los demás números de la array es mayor que K, donde k es un número entero positivo dado. Encuentre el número de anomalías.
Ejemplos:
Input : arr[] = {1, 3, 5}, k = 1
Output : 3
Explanation:
All the numbers in the array are anomalies because
For the number 1 abs(1-3)=2, abs(1-5)=4 which all are greater than 1,
For the number 3 abs(3-1)=2, abs(3-5)=2 which all are again greater than 1
For the number 5 abs(5-1)=4, abs(5-3)=2 which all are again greater than 1
So there are 3 anomalies.
Input : arr[] = {7, 1, 8}, k = 5
Output : 1
Enfoque simple:
simplemente verificamos para cada número si satisface la condición dada, es decir, la diferencia absoluta es mayor que K o no con cada uno de los otros números.
C++
// A simple C++ solution to count anomalies in
// an array.
#include<iostream>
using namespace std;
int countAnomalies(int arr[], int n, int k)
{
int res = 0;
for (int i=0; i<n; i++)
{
int j;
for (j=0; j<n; j++)
if (i != j && abs(arr[i] - arr[j]) <= k)
break;
if (j == n)
res++;
}
return res;
}
int main()
{
int arr[] = {7, 1, 8}, k = 5;
int n = sizeof(arr)/sizeof(arr[0]);
cout << countAnomalies(arr, n, k);
return 0;
}
Java
// A simple java solution to count
// anomalies in an array.
class GFG
{
static int countAnomalies(int arr[],
int n, int k)
{
int res = 0;
for (int i = 0; i < n; i++)
{
int j;
for (j = 0; j < n; j++)
if (i != j && Math.abs(arr[i] -
arr[j]) <= k)
break;
if (j == n)
res++;
}
return res;
}
// Driver code
public static void main(String args[])
{
int arr[] = {7, 1, 8}, k = 5;
int n = arr.length;
System.out.println(countAnomalies(arr, n, k));
}
}
// This code is contributed by ANKITRAI1
Python3
# A simple Python3 solution to # count anomalies in an array. def countAnomalies(arr, n, k): res = 0 for i in range(0, n): j = 0 while j < n: if i != j and abs(arr[i] - arr[j]) <= k: break j += 1 if j == n: res += 1 return res # Driver Code if __name__ == "__main__": arr = [7, 1, 8] k = 5 n = len(arr) print(countAnomalies(arr, n, k)) # This code is contributed by Rituraj Jain
C#
// A simple C# solution to count
// anomalies in an array.
using System;
class GFG
{
static int countAnomalies(int[] arr,
int n, int k)
{
int res = 0;
for (int i = 0; i < n; i++)
{
int j;
for (j = 0; j < n; j++)
if (i != j && Math.Abs(arr[i] -
arr[j]) <= k)
break;
if (j == n)
res++;
}
return res;
}
// Driver code
public static void Main()
{
int[] arr = {7, 1, 8};
int k = 5;
int n = arr.Length;
Console.WriteLine(countAnomalies(arr, n, k));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// A simple PHP solution to count
// anomalies in an array.
function countAnomalies(&$arr, $n, $k)
{
$res = 0;
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
if ($i != $j && abs($arr[$i] -
$arr[$j]) <= $k)
break;
if ($j == $n)
$res++;
}
return $res;
}
// Driver Code
$arr = array(7, 1, 8);
$k = 5;
$n = sizeof($arr);
echo countAnomalies($arr, $n, $k);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// A simple javascript solution to count
// anomalies in an array.
function countAnomalies(arr,n,k)
{
let res = 0;
for (let i = 0; i < n; i++)
{
let j;
for (j = 0; j < n; j++)
if (i != j && Math.abs(arr[i] -
arr[j]) <= k)
break;
if (j == n)
res++;
}
return res;
}
// Driver code
let arr=[7, 1, 8];
let k = 5;
let n = arr.length;
document.write(countAnomalies(arr, n, k));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1
Complejidad temporal: O(n * n)
Enfoque eficiente utilizando la búsqueda binaria
1) Ordenar la array.
2) Para cada elemento, encuentre el elemento más grande mayor que él y el elemento más pequeño mayor que él. Podemos encontrar estos dos en tiempo O (Log n) usando la búsqueda binaria. Si la diferencia entre estos dos elementos es mayor que k, incrementamos el resultado.
Requisitos previos para el siguiente código C++: lower_bound en C++ , upper_bound en C++ .
C++
#include<bits/stdc++.h>
using namespace std;
int countAnomalies(int a[], int n, int k)
{
// Sort the array so that we can apply binary
// search.
sort(a, a+n);
// One by one check every element if it is
// anomaly or not using binary search.
int res = 0;
for (int i=0; i<n; i++)
{
int *u = upper_bound(a, a+n, a[i]);
// If arr[i] is not largest element and
// element just greater than it is within
// k, then return false.
if (u != a+n && ((*u) - a[i]) <= k)
continue;
int *s = lower_bound(a, a+n, a[i]);
// If there are more than one occurrences
// of arr[i], return false.
if (u - s > 1)
continue;
// If arr[i] is not smallest element and
// just smaller element is not k distance away
if (s != a && (*(s - 1) - a[i]) <= k)
continue;
res++;
}
return res;
}
int main()
{
int arr[] = {7, 1, 8}, k = 5;
int n = sizeof(arr)/sizeof(arr[0]);
cout << countAnomalies(arr, n, k);
return 0;
}
Java
import java.util.*;
class GFG
{
static int countAnomalies(int a[], int n, int k)
{
// Sort the array so that we can apply binary
// search.
Arrays.sort(a);
// One by one check every element if it is
// anomaly or not using binary search.
int res = 0;
for (int i = 0; i < n; i++)
{
int u = upper_bound(a, 0, n, a[i]);
// If arr[i] is not largest element and
// element just greater than it is within
// k, then return false.
if (u < n && a[u] - a[i] <= k)
continue;
int s = lower_bound(a, 0, n, a[i]);
// If there are more than one occurrences
// of arr[i], return false.
if (u - s > 1)
continue;
// If arr[i] is not smallest element and
// just smaller element is not k distance away
if (s > 0 && a[s - 1] - a[i] <= k)
continue;
res++;
}
return res;
}
static int lower_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int upper_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
public static void main(String[] args)
{
int arr[] = { 7, 1, 8 }, k = 5;
int n = arr.length;
System.out.print(countAnomalies(arr, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach def countAnomalies(a, n, k): # Sort the array so that # we can apply binary # search. a = sorted(a); # One by one check every # element if it is anomaly # or not using binary search. res = 0; for i in range(n): u = upper_bound(a, 0, n, a[i]); # If arr[i] is not largest # element and element just # greater than it is within # k, then return False. if (u < n and a[u] - a[i] <= k): continue; s = lower_bound(a, 0, n, a[i]); # If there are more than # one occurrences of arr[i], # return False. if (u - s > 1): continue; # If arr[i] is not smallest # element and just smaller # element is not k distance away if (s > 0 and a[s - 1] - a[i] <= k): continue; res += 1; return res; def lower_bound(a, low, high, element): while (low < high): middle = int(low + int(high - low) / 2); if (element > a[middle]): low = middle + 1; else: high = middle; return low; def upper_bound(a, low, high, element): while (low < high): middle = int(low + (high - low) / 2); if (a[middle] > element): high = middle; else: low = middle + 1; return low; # Driver code if __name__ == '__main__': arr = [7, 1, 8] k = 5; n = len(arr); print(countAnomalies(arr, n, k)); # This code is contributed by shikhasingrajput
C#
using System;
class GFG{
static int countAnomalies(int []a, int n, int k)
{
// Sort the array so that we can
// apply binary search.
Array.Sort(a);
// One by one check every element if it is
// anomaly or not using binary search.
int res = 0;
for(int i = 0; i < n; i++)
{
int u = upper_bound(a, 0, n, a[i]);
// If arr[i] is not largest element and
// element just greater than it is within
// k, then return false.
if (u < n && a[u] - a[i] <= k)
continue;
int s = lower_bound(a, 0, n, a[i]);
// If there are more than one occurrences
// of arr[i], return false.
if (u - s > 1)
continue;
// If arr[i] is not smallest element and
// just smaller element is not k distance away
if (s > 0 && a[s - 1] - a[i] <= k)
continue;
res++;
}
return res;
}
static int lower_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int upper_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 7, 1, 8 };
int k = 5;
int n = arr.Length;
Console.Write(countAnomalies(arr, n, k));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
function countAnomalies(a, n, k)
{
// Sort the array so that we can apply binary
// search.
a.sort();
// One by one check every element if it is
// anomaly or not using binary search.
let res = 0;
for (let i = 0; i < n; i++)
{
let u = upper_bound(a, 0, n, a[i]);
// If arr[i] is not largest element and
// element just greater than it is within
// k, then return false.
if (u < n && a[u] - a[i] <= k)
continue;
let s = lower_bound(a, 0, n, a[i]);
// If there are more than one occurrences
// of arr[i], return false.
if (u - s > 1)
continue;
// If arr[i] is not smallest element and
// just smaller element is not k distance away
if (s > 0 && a[s - 1] - a[i] <= k)
continue;
res++;
}
return res;
}
function lower_bound(a, low,
high, element)
{
while (low < high)
{
let middle = low + Math.floor((high - low) / 2);
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
function upper_bound(a, low, high, element)
{
while (low < high)
{
let middle = low + Math.floor((high - low) / 2);
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
let arr = [ 7, 1, 8 ], k = 5;
let n = arr.length;
document.write(countAnomalies(arr, n, k));
</script>
Producción:
1
Complejidad de tiempo: O(n Log n)
Otra solución eficiente para k pequeña
1) Inserte todos los valores de la array en una tabla hash.
2) Recorra la array nuevamente y para cada valor arr[i], busque cada valor desde arr[i] – k hasta arr[i] + k (excluyendo arr[i]). Si no se encuentra ninguno de los elementos, entonces arr[i] es una anomalía.
Complejidad de tiempo: O(nk)