arrays - repetidos - llenar vector sin repetir numeros c++

Entrevista de Google: Encuentre todas las subsecuencias contiguas en una matriz dada de enteros, cuya suma cae en el rango dado. ¿Podemos hacerlo mejor que O(n ^ 2)?

Question

Dada una matriz de enteros y un rango (bajo, alto), encuentre todas las subsecuencias contiguas en la matriz que tengan suma en el rango.

¿Hay una solución mejor que O (n ^ 2)?

Intenté mucho pero no pude encontrar una solución mejor que O (n ^ 2). Por favor, ayúdeme a encontrar una mejor solución o confirme que esto es lo mejor que podemos hacer.

Esto es lo que tengo ahora, estoy asumiendo que el rango se define como [lo, hi] .

public static int numOfCombinations(final int[] data, final int lo, final int hi, int beg, int end) {
    int count = 0, sum = data[beg];

    while (beg < data.length && end < data.length) {
       if (sum > hi) {
          break;
       } else {
          if (lo <= sum && sum <= hi) {
            System.out.println("Range found: [" + beg + ", " + end + "]");
            ++count;
          }
          ++end;
          if (end < data.length) {
             sum += data[end];
          }
       }
    }
    return count;
}

public static int numOfCombinations(final int[] data, final int lo, final int hi) {
    int count = 0;

    for (int i = 0; i < data.length; ++i) {
        count += numOfCombinations(data, lo, hi, i, i);
    }

    return count;
}

Answer 1

A partir de este problem : encuentra todas las subsecuencias contiguas que suman a x. Lo que necesitamos es algo similar.

Para cada índice i, podemos calcular la suma del segmento de 0 a i, que es x. Entonces, el problema ahora es que necesitamos encontrar de 0 a i - 1, cuántos segmentos tienen una suma de (x - baja) a (x - alta), y debería ser más rápida que O (n). Así que hay varias estructuras de datos que lo ayudan a hacer eso en O (logn), que son el árbol de Fenwick y el árbol de intervalo .

Entonces, lo que tenemos que hacer es:

• Iterando a través de todos los índices de 0 a n (n es el tamaño de la matriz).

• En el índice ith, calcule, comenzando de 0 a ith índice, la suma x, consulte el árbol para obtener el total de ocurrencias de números que caen en el rango (x - alto, x - bajo).

• Añade x al árbol.

Entonces la complejidad del tiempo será O (n log n)

Answer 2

Debes usar una programación dinámica simple y una búsqueda binaria. Para encontrar la cuenta:

    from bisect import bisect_left, bisect_right

    def solve(A, start, end):
        """
        O(n lg n) Binary Search
        Bound:
        f[i] - f[j] = start
        f[i] - f[j''] = end
        start < end
        f[j] > f[j'']

        :param A: an integer array
        :param start: lower bound
        :param end: upper bound 
        :return:
        """
        n = len(A)
        cnt = 0
        f = [0 for _ in xrange(n+1)]

        for i in xrange(1, n+1):
            f[i] = f[i-1]+A[i-1]  # sum from left

        f.sort()
        for i in xrange(n+1):
            lo = bisect_left(f, f[i]-end, 0, i)
            hi = bisect_right(f, f[i]-start, 0, i)
            cnt += hi-lo

        return cnt

https://github.com/algorhythms/LintCode/blob/master/Subarray%20Sum%20II.py

Para encontrar los resultados en lugar del recuento, solo necesita otra tabla hash para almacenar la asignación de la lista de índices original (no clasificada) f [i] ->.

Aclamaciones.

Answer 3

Esta es la forma en que puede obtener O (nlogn) si solo hay números positivos:

1. Evaluate cumulative sum of array
2. for i  find total sum[j] in (sum[i]+low,sum[i]+high) using binary search
3. Total = Total + count
4. do 3 to 5 for all i

Complejidad del tiempo: -

Cumulative sum is O(N)
Finding sums in range is O(logN) using binary search
Total Time complexity is O(NlogN)

Answer 4

Si todos los enteros no son negativos, entonces se puede hacer en tiempo O(max(size-of-input,size-of-output)) . Esto es óptimo.

Aquí está el algoritmo en C.

void interview_question (int* a, int N, int lo, int hi)
{
  int sum_bottom_low = 0, sum_bottom_high = 0,
      bottom_low = 0, bottom_high = 0,
      top = 0;
  int i;

  if (lo == 0) printf ("[0 0) ");
  while (top < N)
  {
    sum_bottom_low += a[top];
    sum_bottom_high += a[top];
    top++;
    while (sum_bottom_high >= lo && bottom_high <= top)
    {
      sum_bottom_high -= a[bottom_high++];
    }
    while (sum_bottom_low > hi && bottom_low <= bottom_high)
    {
      sum_bottom_low -= a[bottom_low++];
    }
    // print output
    for (i = bottom_low; i < bottom_high; ++i)
      printf ("[%d %d) ", i, top);
  }
  printf("/n");
}

Excepto por el último bucle marcado como "salida de impresión", cada operación se ejecuta O (N) veces; el último bucle se ejecuta una vez para cada intervalo impreso. Si solo necesitamos contar los intervalos y no imprimirlos, todo el algoritmo se convierte en O(N) .

Si se permiten números negativos, entonces O(N^2) es difícil de superar (podría ser imposible).

Answer 5

O (n) solución de tiempo:

Puede extender la idea de ''dos ​​punteros'' para la versión ''exacta'' del problema. Mantendremos las variables b manera que todos los intervalos en la forma xs[i,a), xs[i,a+1), ..., xs[i,b-1) tengan una suma en el rango buscado [lo, hi] .

a, b = 0, 0
for i in range(n):
    while a != (n+1) and sum(xs[i:a]) < lo:
        a += 1
    while b != (n+1) and sum(xs[i:b]) <= hi:
        b += 1
    for j in range(a, b):
        print(xs[i:j])

Esto es en realidad O(n^2) debido a la sum , pero podemos arreglarlo fácilmente calculando primero las sumas de los prefijos ps manera que ps[i] = sum(xs[:i]) . Entonces la sum(xs[i:j]) es simplemente ps[j]-ps[i] .

Este es un ejemplo de cómo ejecutar el código anterior en [2, 5, 1, 1, 2, 2, 3, 4, 8, 2] con [lo, hi] = [3, 6] :

[5]
[5, 1]
[1, 1, 2]
[1, 1, 2, 2]
[1, 2]
[1, 2, 2]
[2, 2]
[2, 3]
[3]
[4]

Esto se ejecuta en el tiempo O(n + t) , donde t es el tamaño de la salida. Como algunos han notado, la salida puede ser tan grande como t = n^2 , es decir, si todas las subsecuencias contiguas coinciden.

Si permitimos escribir la salida en un formato comprimido (los pares de salida a,b de los cuales todas las subsecuencias son contiguas) podemos obtener un algoritmo de tiempo O(n) puro.

Answer 6

yes in my opinion it can be in O(n)

struct subsequence
{
int first,last,sum;
}s;

function(array,low,high)
{
int till_max=0;
s.first=0;s.last=0;s.sum=0;
for(i=low;i<high;i++)
{

if(till_max+array[i]>array[i])
{
s.first=s.first;
s.last=i;
till_max+=array[i];
}
else
{
s.first=i;
s.last=i;
till_max=array[i];
}
if(till_max in range)
{
s.sum=till_max;
   printf("print values between first=%d and last=%d and sum=%d",s.first,s.last,s.sum);
}
}
}