Dada una matriz con 100 elementos (números del 0 al 99), si saco un elemento aleatorio, ¿cómo encontrarías el que saqué? ¿Cómo resolvería esto si 1: la matriz está ordenada o 2: la matriz no está ordenada?

Si la matriz está ordenada, puede atravesarla pero eso le daría una complejidad de tiempo lineal (O (n)).
Puede usar la búsqueda binaria para encontrar el elemento que falta en la complejidad de tiempo logarítmico (O (log n)).
La idea es que al eliminar un elemento, la condición a [i] = ya no se mantendría. Por lo tanto, verifique el elemento del medio para ver si cumple con la relación mencionada anteriormente.

Si un [medio]> medio marca la mitad izquierda
De lo contrario, marque la mitad derecha

//Array is sorted
int find_missing(int a[], int n)
{
int low = 0 , mid, high = n-1; while (low <= high)
{
mid = (low + high)/2;
if (a[mid] > mid)
{
high = mid-1;
}
else
{
low = mid+1;
}
} return low;
}

//Array is sorted
int find_missing(int a[], int n)
{
int low = 0 , mid, high = n-1; while (low <= high)
{
mid = (low + high)/2;
if (a[mid] > mid)
{
high = mid-1;
}
else
{
low = mid+1;
}
} return low;
}

//Array is sorted
int find_missing(int a[], int n)
{
int low = 0 , mid, high = n-1; while (low <= high)
{
mid = (low + high)/2;
if (a[mid] > mid)
{
high = mid-1;
}
else
{
low = mid+1;
}
} return low;
}

Si la matriz no está ordenada, el método mencionado por Rohit Joshi funcionará bien siempre que la suma no desborde el tamaño entero máximo. Si el número de elementos es grande, la suma podría desbordarse. En ese caso podemos usar la propiedad XOR (a XOR a = 0, 0 XOR a = a).

X = 0 XOR 1 XOR 2 XOR …… XOR (n-1) XOR n
Y = XOR de todos los elementos de la matriz (elementos n-1)

X XOR Y le daría el número faltante porque todo el número aparecerá dos veces excepto el número faltante que aparecerá una vez. La complejidad será O (n).

//Array is not sorted
int find_missing(int a[], int n)
{
int i;
int X = 0, Y = 0;

para (i = 0; i <= n; i ++)
{
X = X ^ i;
}

para (i = 0; i <n; i ++)
{
Y = Y ^ a [i];
}

devuelve X ^ Y;
}

Supongo que lo que está pidiendo es un número perdido en una lista , donde se le da una lista de enteros en un rango y falta uno de los números.

U puede hacer esto simplemente usando la fórmula de suma o la que enumeré a continuación, ambas requieren tiempo O (n).

No importa si la matriz está ordenada o no.

Recuerde, exclusivo o (^)
0 Xo 0 = 0; 0 Xo 1 = 1; 1 X o 0 = 1; 1 Xo 1 = 0

Digamos que la matriz dada es {0,1,2,4,5} es decir, el no faltante. es 3.
Ahora la matriz debería ser {0,1,2,3,4,5}
Si encontramos una manera de Xor ambas matrices 0 ^ 0 = 0,1 ^ 1 = 0 y así sucesivamente
finalmente nos quedaremos con 0 ^ 0 ^ 0 ^ 3 ^ 0 ^ 0 = 0 ^ 3 = 3 (el número que falta)
[Número ^ Número = 0; Número ^ 0 = Número]

x1 = a [0], x2 = 0;

for (i = 1; i x1 = x1 ^ a [i] (recuerde que en [i] falta uno de los elementos)

para (j = 1; j <= n; j ++)
x2 = x2 ^ j; (todos los elementos del 0 al 99)

volver x1 ^ x2;
Nos quedaremos con 0 ^ (número faltante) = número faltante.

  1. ordene la matriz no ordenada y aplique el algoritmo establecido. oO (nlogn)
  2. sumarlos y restarlo de 4950 (suma de 0 a 99) O (n)
  3. cree un hashset y coloque enteros de 0 a 99 en él y ahora tome elementos de matriz sin clasificar, intente poner en hashset si ya existe, elimine element.repeat para todos los elementos. tiempo O (n) espacio O (n)

Simplemente adelante y suma los números. La suma esperada es (99 * 100) / 2 como en este caso ya que los números comienzan desde cero.

Si la suma coincide con la que eliminó Cero, la diferencia entre la suma esperada y la suma obtenida.

Creo que tu pregunta es muy ambigua. Si quiere decir que tiene una matriz y puede tomar un puntero pero no desea acceder al contenido del puntero que recogió, sino que desea estimar el valor contenido allí,

a) si la matriz no está ordenada, ni siquiera intentaría resolver este problema, ya que podría necesitar examinar el contenido de otros 99 punteros
b) si está ordenado, entonces su simpe, (puntero recogido: el puntero al primer elemento de la matriz) …