unidimensionales resueltos pseint programacion matrices ejercicios ejemplos arreglos algoritmos arrays algorithm big-o puzzle

arrays - pseint - matrices en c++ ejercicios resueltos



Algoritmo para determinar si la matriz contiene n... n+m? (30)

Vi esta pregunta en Reddit, y no se presentaron soluciones positivas, y pensé que sería una pregunta perfecta para hacer aquí. Esto fue en un hilo sobre preguntas de la entrevista:

Escriba un método que tome una matriz int de tamaño m, y devuelve (verdadero / falso) si la matriz consta de los números n ... n + m-1, todos los números en ese rango y solo los números en ese rango. La matriz no está garantizada para ser ordenada. (Por ejemplo, {2,3,4} devolvería verdadero. {1,3,1} devolvería falso, {1,2,4} devolvería falso.

El problema que tuve con este es que mi entrevistador me pedía que optimizara (O (n) más rápido, menos memoria, etc.) hasta el punto en que afirmaba que podía hacerlo en una pasada de la matriz usando una cantidad constante de memoria. Nunca pensé eso.

Junto con sus soluciones, indique si suponen que la matriz contiene elementos únicos. Indique también si su solución asume que la secuencia comienza en 1. (He modificado ligeramente la pregunta para permitir casos en los que va 2, 3, 4 ...)

editar: ahora soy de la opinión de que no existe un algoritmo lineal en el tiempo y constante en el espacio que maneje duplicados. ¿Alguien puede verificar esto?

El problema duplicado se reduce a la prueba para ver si la matriz contiene duplicados en O (n) tiempo, O (1) espacio. Si esto se puede hacer, simplemente puede probar primero y, si no hay duplicados, ejecutar los algoritmos publicados. Entonces, ¿puedes probar si hay engaños en O (n) time O (1) space?

¿Por qué las otras soluciones usan una suma de cada valor? Creo que esto es arriesgado, porque cuando se juntan O (n) elementos en un número, se está utilizando técnicamente más de O (1) de espacio.

O (1) indica espacio constante que no cambia por el número de n. No importa si es 1 o 2 variables, siempre que sea un número constante. ¿Por qué dices que es más que O (1) espacio? Si está calculando la suma de n números al acumularla en una variable temporal, de todos modos estaría usando exactamente 1 variable.

Comentando en una respuesta porque el sistema no me permite escribir comentarios todavía.

Actualización (en respuesta a los comentarios): en esta respuesta quise decir O (1) espacio dondequiera que se haya omitido "espacio" o "tiempo". El texto citado es una parte de una respuesta anterior a la que responde.

Contraejemplo para el algoritmo XOR .

(no se puede publicar como un comentario)

@popopome

Para a = {0, 2, 7, 5,} devuelve true (significa que a es una permutación del rango [0, 4) ], pero debe devolver false en este caso ( a obviamente, no es una permutatación de [0, 4) ).

Otro ejemplo de contador: {0, 0, 1, 3, 5, 6, 6} : todos los valores están dentro del rango pero hay duplicados.

Podría implementar incorrectamente la idea (o las pruebas) de popopome, por lo tanto, aquí está el código:

bool isperm_popopome(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, no restrictions on n, no overflow, a[] may be readonly */ int even_xor = 0; int odd_xor = 0; for (int i = 0; i < m; ++i) { if (a[i] % 2 == 0) // is even even_xor ^= a[i]; else odd_xor ^= a[i]; const int b = i + n; if (b % 2 == 0) // is even even_xor ^= b; else odd_xor ^= b; } return (even_xor == 0) && (odd_xor == 0); }

Versión AC del pseudocódigo de b3

(para evitar malas interpretaciones del pseudo-código)

Ejemplo de contador: {1, 1, 2, 4, 6, 7, 7} .

int pow_minus_one(int power) { return (power % 2 == 0) ? 1 : -1; } int ceil_half(int n) { return n / 2 + (n % 2); } bool isperm_b3_3(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, doesn''t use n possible overflow in sum a[] may be readonly */ int altsum = 0; int mina = INT_MAX; int maxa = INT_MIN; for (int i = 0; i < m; ++i) { const int v = a[i] - n + 1; // [n, n+m-1] -> [1, m] to deal with n=0 if (mina > v) mina = v; if (maxa < v) maxa = v; altsum += pow_minus_one(v) * v; } return ((maxa-mina == m-1) and ((pow_minus_one(mina + m-1) * ceil_half(mina + m-1) - pow_minus_one(mina-1) * ceil_half(mina-1)) == altsum)); }

AC version of Kent Fredric''s Ruby solution

(to facilitate testing)

Counter-example (for C version): {8, 33, 27, 30, 9, 2, 35, 7, 26, 32, 2, 23, 0, 13, 1, 6, 31, 3, 28, 4, 5, 18, 12, 2, 9, 14, 17, 21, 19, 22, 15, 20, 24, 11, 10, 16, 25}. Here n=0, m=35. This sequence misses 34 and has two 2 .

It is an O(m) in time and O(1) in space solution.

Out-of-range values are easily detected in O(n) in time and O(1) in space, therefore tests are concentrated on in-range (means all values are in the valid range [n, n+m) ) sequences. Otherwise {1, 34} is a counter example (for C version, sizeof(int)==4, standard binary representation of numbers).

The main difference between C and Ruby version: << operator will rotate values in C due to a finite sizeof(int), but in Ruby numbers will grow to accomodate the result eg,

Ruby: 1 << 100 # -> 1267650600228229401496703205376

C: int n = 100; 1 << n // -> 16

In Ruby: check_index ^= 1 << i; is equivalent to check_index.setbit(i) . The same effect could be implemented in C++: vector<bool> v(m); v[i] = true;

bool isperm_fredric(int m; int a[m], int m, int n) { /** O(m) in time (single pass), O(1) in space, no restriction on n, ?overflow? a[] may be readonly */ int check_index = 0; int check_value = 0; int min = a[0]; for (int i = 0; i < m; ++i) { check_index ^= 1 << i; check_value ^= 1 << (a[i] - n); // if (a[i] < min) min = a[i]; } check_index <<= min - n; // min and n may differ e.g., // {1, 1}: min=1, but n may be 0. return check_index == check_value; }

Values of the above function were tested against the following code:

bool *seen_isperm_trusted = NULL; bool isperm_trusted(int m; int a[m], int m, int n) { /** O(m) in time, O(m) in space */ for (int i = 0; i < m; ++i) // could be memset(s_i_t, 0, m*sizeof(*s_i_t)); seen_isperm_trusted[i] = false; for (int i = 0; i < m; ++i) { if (a[i] < n or a[i] >= n + m) return false; // out of range if (seen_isperm_trusted[a[i]-n]) return false; // duplicates else seen_isperm_trusted[a[i]-n] = true; } return true; // a[] is a permutation of the range: [n, n+m) }

Input arrays are generated with:

void backtrack(int m; int a[m], int m, int nitems) { /** generate all permutations with repetition for the range [0, m) */ if (nitems == m) { (void)test_array(a, nitems, 0); // {0, 0}, {0, 1}, {1, 0}, {1, 1} } else for (int i = 0; i < m; ++i) { a[nitems] = i; backtrack(a, m, nitems + 1); } }

Aquí hay una solución de trabajo en O (n)

Esto es usando el pseudocódigo sugerido por Hazzen más algunas de mis propias ideas. También funciona para números negativos y no requiere ningún elemento de suma de cuadrados.

function testArray($nums, $n, $m) { // check the sum. PHP offers this array_sum() method, but it''s // trivial to write your own. O(n) here. if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) { return false; // checksum failed. } for ($i = 0; $i < $m; ++$i) { // check if the number is in the proper range if ($nums[$i] < $n || $nums[$i] >= $n + $m) { return false; // value out of range. } while (($shouldBe = $nums[$i] - $n) != $i) { if ($nums[$shouldBe] == $nums[$i]) { return false; // duplicate } $temp = $nums[$i]; $nums[$i] = $nums[$shouldBe]; $nums[$shouldBe] = $temp; } } return true; // huzzah! } var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5)); // true var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5)); // true var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5)); // false - out of range var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5)); // false - checksum fail var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5)); // false - dupe var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true

La implementación del algoritmo Hazzen en C

#include<stdio.h> #define swapxor(a,i,j) a[i]^=a[j];a[j]^=a[i];a[i]^=a[j]; int check_ntom(int a[], int n, int m) { int i = 0, j = 0; for(i = 0; i < m; i++) { if(a[i] < n || a[i] >= n+m) return 0; //invalid entry j = a[i] - n; while(j != i) { if(a[i]==a[j]) return -1; //bucket already occupied. Dupe. swapxor(a, i, j); //faster bitwise swap j = a[i] - n; if(a[i]>=n+m) return 0; //[NEW] invalid entry } } return 200; //OK } int main() { int n=5, m=5; int a[] = {6, 5, 7, 9, 8}; int r = check_ntom(a, n, m); printf("%d", r); return 0; }

Editar: cambio realizado en el código para eliminar el acceso ilegal a la memoria.

Product of m consecutive numbers is divisible by m! [ m factorial ]

so in one pass you can compute the product of the m numbers, also compute m! and see if the product modulo m ! is zero at the end of the pass

I might be missing something but this is what comes to my mind ...

something like this in python

my_list1 = [9,5,8,7,6]

my_list2 = [3,5,4,7]

def consecutive(my_list):

count = 0 prod = fact = 1 for num in my_list: prod *= num count +=1 fact *= count if not prod % fact: return 1 else: return 0

print consecutive(my_list1)

print consecutive(my_list2)

HotPotato ~$ python m_consecutive.py

1

0

¿Por qué las otras soluciones usan una suma de cada valor? Creo que esto es arriesgado, porque cuando se juntan O (n) elementos en un número, se está utilizando técnicamente más de O (1) de espacio.

Método más simple:

Paso 1, averigua si hay duplicados. No estoy seguro si esto es posible en O (1) espacio. De todos modos, devuelve falso si hay duplicados.

Paso 2, repita la lista y realice un seguimiento de los elementos más bajos y más altos .

Paso 3, ¿(el más alto - el más bajo) es igual a m? Si es así, devuelve verdadero.

Al trabajar con a[i] % a.length lugar de a[i] , reduce el problema a la necesidad de determinar que tiene los números 0 a a.length - 1 .

Damos por sentada esta observación e intentamos verificar si la matriz contiene [0, m).

Encuentre el primer nodo que no está en su posición correcta, por ejemplo

0 1 2 3 7 5 6 8 4 ; the original dataset (after the renaming we discussed) ^ `---this is position 4 and the 7 shouldn''t be here

Cambia ese número a donde debería estar. es decir, intercambie el 7 con el 8 :

0 1 2 3 8 5 6 7 4 ; | `--------- 7 is in the right place. `--------------- this is now the ''current'' position

Ahora repetimos esto. Mirando nuevamente nuestra posición actual preguntamos:

"¿Es este el número correcto para aquí?"

  • Si no, lo cambiamos a su lugar correcto.
  • Si está en el lugar correcto, nos movemos a la derecha y hacemos esto de nuevo.

Siguiendo esta regla de nuevo, obtenemos:

0 1 2 3 4 5 6 7 8 ; 4 and 8 were just swapped

Esto aumentará gradualmente la lista correctamente de izquierda a derecha, y cada número se moverá a lo sumo una vez, y por lo tanto esto es O (n).

Si hay engaños, lo notaremos tan pronto haya un intento de cambiar un número backwards en la lista.

Cualquier algoritmo de paso único requiere Omega (n) bits de almacenamiento.

Supongamos, por el contrario, que existe un algoritmo de una pasada que utiliza o (n) bits. Como solo hace una pasada, debe resumir los primeros n / 2 valores en o (n) espacio. Como hay C (n, n / 2) = 2 ^ Theta (n) conjuntos posibles de n / 2 valores tomados de S = {1, ..., n}, existen dos conjuntos distintos A y B de n / 2 valores tales que el estado de la memoria es el mismo después de ambos. Si A ''= S / A es el conjunto de valores "correctos" para complementar A, entonces el algoritmo no puede responder correctamente para las entradas

AA ''- sí

BA ''- no

ya que no puede distinguir el primer caso del segundo.

QED

Dado este -

Escriba un método que tome una matriz int de tamaño m ...

Supongo que es justo concluir que hay un límite superior para m, igual al valor de la int más grande (2 ^ 32 es típico). En otras palabras, aunque m no se especifique como int, el hecho de que la matriz no pueda tener duplicados implica que no puede haber más que el número de valores que puede formar a partir de 32 bits, lo que a su vez implica que m es limitado a ser un int también

Si tal conclusión es aceptable, entonces propongo usar un espacio fijo de (2 ^ 33 + 2) * 4 bytes = 34,359,738,376 bytes = 34,4GB para manejar todos los casos posibles. (Sin contar el espacio requerido por la matriz de entrada y su ciclo).

Por supuesto, para la optimización, primero tomaría en cuenta m, y asignaría solo la cantidad real necesaria, (2 m + 2) * 4 bytes.

Si esto es aceptable para la restricción de espacio O (1) - para el problema establecido - entonces permítame proceder a una propuesta algorítmica ... :)

Suposiciones : matriz de mtsts, positiva o negativa, ninguna mayor que lo que pueden contener 4 bytes. Duplicados son manejados. El primer valor puede ser cualquier int válido. Restringe m como arriba.

Primero , cree una matriz int de longitud 2m-1, ary , y proporcione tres variables int: izquierda , diff y derecha . Tenga en cuenta que hace 2 m + 2 ...

Segundo , tome el primer valor de la matriz de entrada y cópielo a la posición m-1 en la nueva matriz. Inicializa las tres variables.

  • set ary [m-1] - nthVal // n = 0
  • set left = diff = right = 0

En tercer lugar , recorra los valores restantes en la matriz de entrada y haga lo siguiente para cada iteración:

  • establecer diff = nthVal - ary [m-1]
  • if ( diff > m-1 + right || diff <1-m + left ) devuelve false // fuera de límites
  • if ( ary [m-1 + diff ]! = null) return false // duplicate
  • set ary [m-1 + diff ] = nthVal
  • if ( diff > left ) left = diff // limita el límite izquierdo más a la derecha
  • if ( diff < right ) right = diff // limita el límite derecho más a la izquierda

Decidí poner esto en el código, y funcionó.

Aquí hay una muestra de trabajo que usa C #:

public class Program { static bool puzzle(int[] inAry) { var m = inAry.Count(); var outAry = new int?[2 * m - 1]; int diff = 0; int left = 0; int right = 0; outAry[m - 1] = inAry[0]; for (var i = 1; i < m; i += 1) { diff = inAry[i] - inAry[0]; if (diff > m - 1 + right || diff < 1 - m + left) return false; if (outAry[m - 1 + diff] != null) return false; outAry[m - 1 + diff] = inAry[i]; if (diff > left) left = diff; if (diff < right) right = diff; } return true; } static void Main(string[] args) { var inAry = new int[3]{ 2, 3, 4 }; Console.WriteLine(puzzle(inAry)); inAry = new int[13] { -3, 5, -1, -2, 9, 8, 2, 3, 0, 6, 4, 7, 1 }; Console.WriteLine(puzzle(inAry)); inAry = new int[3] { 21, 31, 41 }; Console.WriteLine(puzzle(inAry)); Console.ReadLine(); } }

En Python:

def ispermutation(iterable, m, n): """Whether iterable and the range [n, n+m) have the same elements. pre-condition: there are no duplicates in the iterable """ for i, elem in enumerate(iterable): if not n <= elem < n+m: return False return i == m-1 print(ispermutation([1, 42], 2, 1) == False) print(ispermutation(range(10), 10, 0) == True) print(ispermutation((2, 1, 3), 3, 1) == True) print(ispermutation((2, 1, 3), 3, 0) == False) print(ispermutation((2, 1, 3), 4, 1) == False) print(ispermutation((2, 1, 3), 2, 1) == False)

Es O (m) en el tiempo y O (1) en el espacio. No tiene en cuenta los duplicados.

Solución alternativa:

def ispermutation(iterable, m, n): """Same as above. pre-condition: assert(len(list(iterable)) == m) """ return all(n <= elem < n+m for elem in iterable)

Hace un tiempo escuché acerca de un algoritmo de clasificación muy inteligente de alguien que trabajaba para la compañía telefónica. Tuvieron que ordenar una gran cantidad de números telefónicos. Después de pasar por un conjunto de diferentes estrategias de clasificación, finalmente llegaron a una solución muy elegante: simplemente crearon una matriz de bits y trataron la compensación en la matriz de bits como el número de teléfono. Luego recorrieron su base de datos con una sola pasada, cambiando el bit para cada número a 1. Después de eso, barrieron la matriz de bits una vez, escupiendo los números de teléfono para las entradas que tenían el bit alto.

En ese sentido, creo que puede usar los datos en la matriz en sí como una estructura de metadatos para buscar duplicados. En el peor de los casos, podrías tener una matriz separada, pero estoy bastante seguro de que puedes usar la matriz de entrada si no te importa un poco intercambiar.

Voy a omitir el parámetro n por el momento, b / c que solo confunde cosas - agregar un índice de compensación es bastante fácil de hacer.

Considerar:

for i = 0 to m if (a[a[i]]==a[i]) return false; // we have a duplicate while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i) sum = sum + a[i] next if sum = (n+m-1)*m return true else return false

Esto no es O (n), probablemente más cerca de O (n Log n), pero proporciona espacio constante y puede proporcionar un vector de ataque diferente para el problema.

Si queremos O (n), entonces usar una matriz de bytes y algunas operaciones de bit proporcionará la verificación de duplicación con un n / 32 bytes adicionales de memoria utilizada (asumiendo entradas de 32 bits, por supuesto).

EDITAR: El algoritmo anterior podría mejorarse aún más al agregar la verificación de suma al interior del ciclo, y verificar:

if sum > (n+m-1)*m return false

de esa manera fallará rápidamente.

MI MEJOR OPCIÓN ACTUAL

def uniqueSet( array ) check_index = 0; check_value = 0; min = array[0]; array.each_with_index{ |value,index| check_index = check_index ^ ( 1 << index ); check_value = check_value ^ ( 1 << value ); min = value if value < min } check_index = check_index << min; return check_index == check_value; end

O (n) y Space O (1)

Escribí un guión para combinaciones de fuerza bruta que podrían fallar y no encontré ninguna. Si tiene una matriz que contraviene esta función, dígaselo. :)

@JF Sebastian

No es un verdadero algoritmo hash. Técnicamente, es una matriz booleana compacta altamente eficiente de valores "vistos".

ci = 0, cv = 0 [5,4,3]{ i = 0 v = 5 1 << 0 == 000001 1 << 5 == 100000 0 ^ 000001 = 000001 0 ^ 100000 = 100000 i = 1 v = 4 1 << 1 == 000010 1 << 4 == 010000 000001 ^ 000010 = 000011 100000 ^ 010000 = 110000 i = 2 v = 3 1 << 2 == 000100 1 << 3 == 001000 000011 ^ 000100 = 000111 110000 ^ 001000 = 111000 } min = 3 000111 << 3 == 111000 111000 === 111000

El objetivo principal de esto es que, para "falsificar" la mayoría de los casos problemáticos, uno usa duplicados para hacerlo. En este sistema, XOR lo penaliza por usar el mismo valor dos veces y supone que en su lugar lo hizo 0 veces.

Las advertencias aquí son, por supuesto:

  1. Tanto la longitud de la matriz de entrada como el valor máximo de la matriz están limitados por el valor máximo de $x in ( 1 << $x > 0 )

  2. la eficacia última depende de cómo su sistema subyacente implementa las habilidades para:

    1. cambiar 1 bit n coloca a la derecha.
    2. xor 2 registros. ( where ''registers'' may, depending on implementation, span several registers )

    edit Noted, above statements seem confusing. Assuming a perfect machine, where an "integer" is a register with Infinite precision, which can still perform a ^ b in O(1) time.

But failing these assumptions, one has to start asking the algorithmic complexity of simple math.

  • How complex is 1 == 1 ?, surely that should be O(1) every time right?.
  • What about 2^32 == 2^32 .
  • O(1)? 2^33 == 2^33? Now you''ve got a question of register size and the underlying implementation.
  • Fortunately XOR and == can be done in parallel, so if one assumes infinite precision and a machine designed to cope with infinite precision, it is safe to assume XOR and == take constant time regardless of their value ( because its infinite width, it will have infinite 0 padding. Obviously this doesn''t exist. But also, changing 000000 to 000100 is not increasing memory usage.
  • Yet on some machines , ( 1 << 32 ) << 1 will consume more memory, but how much is uncertain.

Oops! I got caught up in a duplicate question and did not see the already identical solutions here. And I thought I''d finally done something original! Here is a historical archive of when I was slightly more pleased:

Well, I have no certainty if this algorithm satisfies all conditions. In fact, I haven''t even validated that it works beyond a couple test cases I have tried. Even if my algorithm does have problems, hopefully my approach sparks some solutions.

This algorithm, to my knowledge, works in constant memory and scans the array three times. Perhaps an added bonus is that it works for the full range of integers, if that wasn''t part of the original problem.

I am not much of a pseudo-code person, and I really think the code might simply make more sense than words. Here is an implementation I wrote in PHP. Take heed of the comments.

function is_permutation($ints) { /* Gather some meta-data. These scans can be done simultaneously */ $lowest = min($ints); $length = count($ints); $max_index = $length - 1; $sort_run_count = 0; /* I do not have any proof that running this sort twice will always completely sort the array (of course only intentionally happening if the array is a permutation) */ while ($sort_run_count < 2) { for ($i = 0; $i < $length; ++$i) { $dest_index = $ints[$i] - $lowest; if ($i == $dest_index) { continue; } if ($dest_index > $max_index) { return false; } if ($ints[$i] == $ints[$dest_index]) { return false; } $temp = $ints[$dest_index]; $ints[$dest_index] = $ints[$i]; $ints[$i] = $temp; } ++$sort_run_count; } return true; }

Si desea saber la suma de los números [n ... n + m - 1] simplemente use esta ecuación.

var sum = m * (m + 2 * n - 1) / 2;

Eso funciona para cualquier número, positivo o negativo, incluso si n es un decimal.

Suponiendo que solo conoce la longitud de la matriz y puede modificar la matriz, puede hacerlo en O (1) espacio y O (n) tiempo.

El proceso tiene dos pasos sencillos. 1. "ordenar módulo" la matriz. [5,3,2,4] => [4,5,2,3] (O (2n)) 2. Verifique que el vecino de cada valor sea uno más alto que él (módulo) (O (n))

Todo lo que necesitas es como mucho 3 pases a través de la matriz.

El tipo de módulo es la parte "difícil", pero el objetivo es simple. Tome cada valor en la matriz y guárdelo en su propia dirección (longitud del módulo). Esto requiere un pase a través de la matriz, recorriendo cada ubicación para ''desalojar'' su valor al cambiarlo a su ubicación correcta y mover el valor en su destino. Si alguna vez se mueve en un valor que sea congruente con el valor que acaba de expulsar, tiene un duplicado y puede salir temprano. En el peor de los casos, es O (2n).

El cheque es un pase único a través de la matriz que examina cada valor con su próximo vecino más alto. Siempre O (n).

El algoritmo combinado es O (n) + O (2n) = O (3n) = O (n)

Pseudocódigo de mi solución:

foreach(values[]) while(values[i] not congruent to i) to-be-evicted = values[i] evict(values[i]) // swap to its ''proper'' location if(values[i]%length == to-be-evicted%length) return false; // a ''duplicate'' arrived when we evicted that number end while end foreach foreach(values[]) if((values[i]+1)%length != values[i+1]%length) return false end foreach

He incluido la prueba de concepto de código Java a continuación, no es bonita, pero pasa todas las pruebas unitarias que hice para ello. Los llamo ''StraightArray'' porque corresponden a la mano de póker de una escalera recta (secuencia contigua ignorando el palo).

public class StraightArray { static int evict(int[] a, int i) { int t = a[i]; a[i] = a[t%a.length]; a[t%a.length] = t; return t; } static boolean isStraight(int[] values) { for(int i = 0; i < values.length; i++) { while(values[i]%values.length != i) { int evicted = evict(values, i); if(evicted%values.length == values[i]%values.length) { return false; } } } for(int i = 0; i < values.length-1; i++) { int n = (values[i]%values.length)+1; int m = values[(i+1)]%values.length; if(n != m) { return false; } } return true; } }

Vótame si me equivoco, pero creo que podemos determinar si hay duplicados o no usar la varianza. Como conocemos la media de antemano (n + (m-1) / 2 o algo así) podemos resumir los números y el cuadrado de la diferencia para indicar si la suma coincide con la ecuación (mn + m (m-1) ) / 2) y la varianza es (0 + 1 + 4 + ... + (m-1) ^ 2) / m. Si la varianza no coincide, es probable que tengamos un duplicado.

EDITAR: se supone que la varianza es (0 + 1 + 4 + ... + [(m-1) / 2] ^ 2) * 2 / m, porque la mitad de los elementos son menores que la media y la otra mitad mayor que la media.

Si hay un duplicado, un término en la ecuación anterior diferirá de la secuencia correcta, incluso si otro duplicado cancela por completo el cambio en la media. Entonces, la función devuelve verdadera solo si tanto la suma como la varianza coinciden con los valores deseados, que podemos calcular de antemano.

nota : este comentario se basa en el texto original de la pregunta (se ha corregido desde)

Si la pregunta se plantea exactamente como se escribió anteriormente (y no es solo un error tipográfico) y para una matriz de tamaño n, la función debe regresar (Verdadero / Falso) si la matriz consta de los números 1 ... n + 1,

... entonces la respuesta siempre será falsa porque la matriz con todos los números 1 ... n + 1 tendrá el tamaño n + 1 y no n. por lo tanto, la pregunta puede ser respondida en O (1). :)

An array contains N numbers, and you want to determine whether two of the numbers sum to a given number K. For instance, if the input is 8,4, 1,6 and K is 10, the answer is yes (4 and 6). A number may be used twice. Do the following. a. Give an O(N2) algorithm to solve this problem. segundo. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items first. After doing so, you can solve the problem in linear time.) c. Code both solutions and compare the running times of your algorithms. 4.

Any contiguous array [ n, n+1, ..., n+m-1 ] can be mapped on to a ''base'' interval [ 0, 1, ..., m ] using the modulo operator. For each i in the interval, there is exactly one i%m in the base interval and vice versa.

Any contiguous array also has a ''span'' m (maximum - minimum + 1) equal to it''s size.

Using these facts, you can create an "encountered" boolean array of same size containing all falses initially, and while visiting the input array, put their related "encountered" elements to true.

This algorithm is O(n) in space, O(n) in time, and checks for duplicates.

def contiguous( values ) #initialization encountered = Array.new( values.size, false ) min, max = nil, nil visited = 0 values.each do |v| index = v % encountered.size if( encountered[ index ] ) return "duplicates"; end encountered[ index ] = true min = v if min == nil or v < min max = v if max == nil or v > max visited += 1 end if ( max - min + 1 != values.size ) or visited != values.size return "hole" else return "contiguous" end end tests = [ [ false, [ 2,4,5,6 ] ], [ false, [ 10,11,13,14 ] ] , [ true , [ 20,21,22,23 ] ] , [ true , [ 19,20,21,22,23 ] ] , [ true , [ 20,21,22,23,24 ] ] , [ false, [ 20,21,22,23,24+5 ] ] , [ false, [ 2,2,3,4,5 ] ] ] tests.each do |t| result = contiguous( t[1] ) if( t[0] != ( result == "contiguous" ) ) puts "Failed Test : " + t[1].to_s + " returned " + result end end

Bajo la suposición de que no se permiten números menores de uno y no hay duplicados, existe una identidad de suma simple para esto: la suma de números de 1 a m en incrementos de 1 es (m * (m + 1)) / 2 . A continuación, puede sumar la matriz y usar esta identidad.

Puede averiguar si hay un duplicado bajo las garantías anteriores, más la garantía de que ningún número es superior a m o menor que n (que se puede verificar en O(N) )

La idea en pseudo-código:
0) Comience en N = 0
1) Tome el elemento N-ésimo en la lista.
2) Si no está en el lugar correcto si la lista se ha ordenado, compruebe dónde debería estar.
3) Si el lugar donde debería estar ya tiene el mismo número, tiene una estafa - RETORNO VERDADERO
4) De lo contrario, intercambie los números (para poner el primer número en el lugar correcto).
5) Con el número que acaba de intercambiar, ¿está en el lugar correcto?
6) Si no, regrese al paso dos.
7) De lo contrario, comience en el paso uno con N = N + 1. Si esto hubiera pasado el final de la lista, no tiene engaños.

Y, sí, eso se ejecuta en O(N) aunque puede parecerse a O(N ^ 2)

Nota para todos (cosas recogidas de los comentarios)

Esta solución funciona bajo la suposición de que puede modificar la matriz y luego utiliza la ordenación in situ de Radix (que alcanza la velocidad O(N) ).

Se han presentado otras soluciones de mathy, pero no estoy seguro de que hayan sido probadas. Hay un montón de sumas que pueden ser útiles, pero la mayoría se multiplican en la cantidad de bits necesarios para representar la suma, lo que viola la garantía de espacio adicional constante. Tampoco sé si alguno de ellos es capaz de producir un número distinto para un conjunto determinado de números. Creo que una suma de cuadrados podría funcionar, que tiene una fórmula conocida para calcularlo (ver Wolfram''s )

Nueva visión (bueno, más reflexiones que no ayudan a resolverlo pero son interesantes y me voy a la cama):

Por lo tanto, se ha mencionado que tal vez use sum + sum of squares. Nadie sabía si esto funcionaba o no, y me di cuenta de que solo se convierte en un problema cuando (x + y) = (n + m), como el hecho de que 2 + 2 = 1 + 3. Los cuadrados también tienen este problema gracias a Triples pitagóricos (entonces 3 ^ 2 + 4 ^ 2 + 25 ^ 2 == 5 ^ 2 + 7 ^ 2 + 24 ^ 2, y la suma de cuadrados no funciona). Si usamos el último teorema de Fermat , sabemos que esto no puede suceder para n ^ 3. Pero tampoco sabemos si no hay x + y + z = n para esto (a menos que lo hagamos y no lo sé). Así que no hay garantía de que esto tampoco se rompa, y si continuamos por este camino, rápidamente nos quedamos sin partes.

En mi alegría, sin embargo, olvidé notar que puedes romper la suma de cuadrados, pero al hacerlo creas una suma normal que no es válida. No creo que puedas hacer ambas cosas, pero, como se ha observado, no tenemos ninguna prueba de ninguna manera.

Debo decir que encontrar contraejemplos a veces es mucho más fácil que probar cosas. Considere las siguientes secuencias, todas las cuales tienen una suma de 28 y una suma de cuadrados de 140:

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

No pude encontrar ningún ejemplo de longitud 6 o menos. Si desea un ejemplo que tenga los valores mínimos y máximos adecuados, pruebe este de longitud 8:

[1, 3, 3, 4, 4, 5, 8, 8]

Enfoque más simple (modificando la idea de Hazzen):

Una matriz entera de longitud m contiene todos los números de n a n + m-1 exactamente una vez iff

  • cada elemento de la matriz está entre n y n + m-1
  • no hay duplicados

(Motivo: solo hay m valores en el rango entero dado, así que si la matriz contiene m valores únicos en este rango, debe contener cada uno de ellos una vez)

Si puede modificar el conjunto, puede verificar ambos en una pasada a través de la lista con una versión modificada de la idea del algoritmo de hazzen (no es necesario hacer ningún resumen):

  • Para todos los índices de matriz i de 0 a m-1
    1. Si matriz [i] <n o matriz [i]> = n + m => RETORNO FALSO ("valor fuera de rango encontrado")
    2. Calcule j = array [i] - n (esta es la posición basada en 0 de la matriz [i] en una matriz ordenada con valores de n a n + m-1)
    3. Mientras que j no es igual a i
      1. Si list [i] es igual a list [j] => RETURN FALSE ("duplicado encontrado")
      2. Cambiar la lista [i] con la lista [j]
      3. Recalcular j = array [i] - n
  • REGRESAR VERDADERO

No estoy seguro de si la modificación de la matriz original cuenta contra el espacio adicional máximo permitido de O (1), pero si no lo hace, esta debería ser la solución que el póster original quería.

Here is a solution in O(N) time and O(1) extra space for finding duplicates :-

public static boolean check_range(int arr[],int n,int m) { for(int i=0;i<m;i++) { arr[i] = arr[i] - n; if(arr[i]>=m) return(false); } System.out.println("In range"); int j=0; while(j<m) { System.out.println(j); if(arr[j]<m) { if(arr[arr[j]]<m) { int t = arr[arr[j]]; arr[arr[j]] = arr[j] + m; arr[j] = t; if(j==arr[j]) { arr[j] = arr[j] + m; j++; } } else return(false); } else j++; }

Explanation:-

  1. Bring number to range (0,m-1) by arr[i] = arr[i] - n if out of range return false.
  2. for each i check if arr[arr[i]] is unoccupied that is it has value less than m
  3. si es así, cambie (arr [i], arr [arr [i]]) y arr [arr [i]] = arr [arr [i]] + m para indicar que está ocupado
  4. si arr [j] = j y simplemente agrega m e incrementa j
  5. si arr [arr [j]]> = m significa que está ocupado, por lo tanto, el valor actual es duplicado, por lo tanto, devuelve falso.
  6. si arr [j]> = m entonces omita

I like Greg Hewgill''s idea of Radix sorting. To find duplicates, you can sort in O(N) time given the constraints on the values in this array.

For an in-place O(1) space O(N) time that restores the original ordering of the list, you don''t have to do an actual swap on that number; you can just mark it with a flag:

//Java: assumes all numbers in arr > 1 boolean checkArrayConsecutiveRange(int[] arr) { // find min/max int min = arr[0]; int max = arr[0] for (int i=1; i<arr.length; i++) { min = (arr[i] < min ? arr[i] : min); max = (arr[i] > max ? arr[i] : max); } if (max-min != arr.length) return false; // flag and check boolean ret = true; for (int i=0; i<arr.length; i++) { int targetI = Math.abs(arr[i])-min; if (arr[targetI] < 0) { ret = false; break; } arr[targetI] = -arr[targetI]; } for (int i=0; i<arr.length; i++) { arr[i] = Math.abs(arr[i]); } return ret; }

Storing the flags inside the given array is kind of cheating, and doesn''t play well with parallelization. I''m still trying to think of a way to do it without touching the array in O(N) time and O(log N) space. Checking against the sum and against the sum of least squares (arr[i] - arr.length/2.0)^2 feels like it might work. The one defining characteristic we know about a 0...m array with no duplicates is that it''s uniformly distributed; we should just check that.

Now if only I could prove it.

I''d like to note that the solution above involving factorial takes O(N) space to store the factorial itself. N! > 2^N, which takes N bytes to store.

I propose the following:

Choose a finite set of prime numbers P_1,P_2,...,P_K, and compute the occurrences of the elements in the input sequence (minus the minimum) modulo each P_i. The pattern of a valid sequence is known.

For example for a sequence of 17 elements, modulo 2 we must have the profile: [9 8], modulo 3: [6 6 5], modulo 5: [4 4 3 3 3], etc.

Combining the test using several bases we obtain a more and more precise probabilistic test. Since the entries are bounded by the integer size, there exists a finite base providing an exact test. This is similar to probabilistic pseudo primality tests.

S_i is an int array of size P_i, initially filled with 0, i=1..K M is the length of the input sequence Mn = INT_MAX Mx = INT_MIN for x in the input sequence: for i in 1..K: S_i[x % P_i]++ // count occurrences mod Pi Mn = min(Mn,x) // update min Mx = max(Mx,x) // and max if Mx-Mn != M-1: return False // Check bounds for i in 1..K: // Check profile mod P_i Q = M / P_i R = M % P_i Check S_i[(Mn+j) % P_i] is Q+1 for j=0..R-1 and Q for j=R..P_i-1 if this test fails, return False return True

So there is an algorithm that takes O(n^2) that does not require modifying the input array and takes constant space.

First, assume that you know n and m . This is a linear operation, so it does not add any additional complexity. Next, assume there exists one element equal to n and one element equal to n+m-1 and all the rest are in [n, n+m) . Given that, we can reduce the problem to having an array with elements in [0, m) .

Now, since we know that the elements are bounded by the size of the array, we can treat each element as a node with a single link to another element; in other words, the array describes a directed graph. In this directed graph, if there are no duplicate elements, every node belongs to a cycle, that is, a node is reachable from itself in m or less steps. If there is a duplicate element, then there exists one node that is not reachable from itself at all.

So, to detect this, you walk the entire array from start to finish and determine if each element returns to itself in <=m steps. If any element is not reachable in <=m steps, then you have a duplicate and can return false. Otherwise, when you finish visiting all elements, you can return true:

for (int start_index= 0; start_index<m; ++start_index) { int steps= 1; int current_element_index= arr[start_index]; while (steps<m+1 && current_element_index!=start_index) { current_element_index= arr[current_element_index]; ++steps; } if (steps>m) { return false; } } return true;

You can optimize this by storing additional information:

  1. Record sum of the length of the cycle from each element, unless the cycle visits an element before that element, call it sum_of_steps .
  2. For every element, only step m-sum_of_steps nodes out. If you don''t return to the starting element and you don''t visit an element before the starting element, you have found a loop containing duplicate elements and can return false .

This is still O(n^2), eg {1, 2, 3, 0, 5, 6, 7, 4} , but it''s a little bit faster.

The Answer from "nickf" dows not work if the array is unsorted var_dump(testArray(array(5, 3, 1, 2, 4), 1, 5)); //gives "duplicates" !!!!

Also your formula to compute sum([n...n+m-1]) looks incorrect.... the correct formula is (m(m+1)/2 - n(n-1)/2)

ciphwn has it right. It is all to do with statistics. What the question is asking is, in statistical terms, is whether or not the sequence of numbers form a discrete uniform distribution. A discrete uniform distribution is where all values of a finite set of possible values are equally probable. Fortunately there are some useful formulas to determine if a discrete set is uniform. Firstly, to determine the mean of the set (a..b) is (a+b)/2 and the variance is (nn-1)/12. Next, determine the variance of the given set:

variance = sum [i=1..n] (f(i)-mean).(f(i)-mean)/n

and then compare with the expected variance. This will require two passes over the data, once to determine the mean and again to calculate the variance.

Referencias

boolean determineContinuousArray(int *arr, int len) { // Suppose the array is like below: //int arr[10] = {7,11,14,9,8,100,12,5,13,6}; //int len = sizeof(arr)/sizeof(int); int n = arr[0]; int *result = new int[len]; for(int i=0; i< len; i++) result[i] = -1; for (int i=0; i < len; i++) { int cur = arr[i]; int hold ; if ( arr[i] < n){ n = arr[i]; } while(true){ if ( cur - n >= len){ cout << "array index out of range: meaning this is not a valid array" << endl; return false; } else if ( result[cur - n] != cur){ hold = result[cur - n]; result[cur - n] = cur; if (hold == -1) break; cur = hold; }else{ cout << "found duplicate number " << cur << endl; return false; } } } cout << "this is a valid array" << endl; for(int j=0 ; j< len; j++) cout << result[j] << "," ; cout << endl; return true; }

def test(a, n, m): seen = [False] * m for x in a: if x < n or x >= n+m: return False if seen[x-n]: return False seen[x-n] = True return False not in seen print test([2, 3, 1], 1, 3) print test([1, 3, 1], 1, 3) print test([1, 2, 4], 1, 3)

Tenga en cuenta que esto solo hace que una pase por la primera matriz, sin considerar la búsqueda lineal involucrada en not in . :)

También podría haber usado un set Python, pero opté por la solución directa donde las características de rendimiento del set no necesitan ser consideradas.

Actualización: Smashery señaló que había mal interpretado la "cantidad constante de memoria" y esta solución en realidad no resuelve el problema.