Pregunta complicada de la entrevista sobre la búsqueda

Question

Hace poco escuché esta pregunta de un amigo al que se le preguntó esto en una entrevista. No fue capaz de resolverlo y aún no he encontrado ninguna solución eficiente para él. Espero que haya una algorithmist aquí que me pueda mostrar un nuevo enfoque

Pregunta:

Dada una matriz A y un número S', proporcionará un algoritmo eficiente (nlogn) para buscar un número K tal que si todo los elementos en A mayor que K se cambian a K, la suma de todos los elementos en la matriz resultante será S '.

Ejemplo, dado A: [90,30,100,40,20] y S' = 210, K será 60.

Answer 1

escrito en Python, que debe ser bastante legible incluso si usted no sabe el idioma:

#!/usr/bin/env python 

A = [90, 30, 100, 40, 20] 
S = 210 
K = 60 

A = sorted(A) 
prev = 0 
sum = 0 

for index, value in enumerate(A): 
    # What do we need to set all subsequent values to to get the desired sum? 
    solution = (S - sum)/(len(A) - index) 

    # That answer can't be too big or too small. 
    if prev < solution <= value: 
     print solution 

    sum += value 
    prev = value 

Resultado:

60 

Clasificación es O (n registro n) y el ciclo es O ( n). El algoritmo combinado como un todo es por lo tanto O ( n log n).

Answer 2

Primero ordene la lista desde la más pequeña hasta la más grande y descubra por cuánto tiempo. Luego comience a sumar los números uno por uno. En cada paso, también encuentre un límite inferior en lo que podría ser la suma: cuál sería la suma de toda la lista, si todos los demás números que aún no ha agregado son los mismos que el número actual.

En algún punto, este límite inferior de la suma pasará de ser más pequeño que S 'a ser más grande que S', y en ese punto puede hacer algunas operaciones aritméticas para determinar cuál debe ser el corte. ej. (C = suma actual, L = límite inferior en la suma total):

 
start 
[90 30 100 40 20] 
sort 
[20 30 40 90 100] 
start adding up the sum 
C1 = 20 
L1 = 20 + 4*20 = 100 < 210 

C2 = 20 + 30 = 50 
L2 = 50 + 3*30 = 140 < 210 

C3 = 50 + 40 = 90 
L3 = 90 + 2*40 = 170 < 210 

C4 = 90 + 90 = 180 
L4 = 180 + 1*90 = 270 > 210 //too big! 

S' = C3 + K*2 
therefore 
K = (S'-C3)/2 = 60 

Answer 3

Aquí está mi solución. Básicamente estoy haciendo una búsqueda binaria para el valor de K en el rango [0, max (A)]. Si bien esto evita tener que ordenar la matriz primero (preservando así la matriz original), sigue siendo O (n * log (k)) donde n es el número de elementos en A y k es el valor máximo en A.

#! /usr/bin/env python 
from itertools import imap 

def findK(A,S): 
    lo,hi=0,max(A) 
    while lo<hi: 
     mid=(hi+lo+1)>>1 
     result=sum(imap(lambda x: x if x<mid else mid,A)) 
     if result<=S: 
      lo=mid 
     else: 
      hi=mid-1 
    return lo 

if __name__=='__main__': 
    print findK(A=[90,30,100,40,20],S = 210)    

Answer 4

Esto se puede realizar sin ordenar en tiempo O (n) utilizando una variación en la selección de tiempo lineal de la siguiente manera (tenga en cuenta que los tiempos de ejecución de las iteraciones del ciclo while forman una serie geométrica; la subrutina de partición divide una rango de una matriz, de menor a superior, en elementos de menor o mayor que el elemento de mediados de rango, y el tiempo de ejecución es proporcional al tamaño de la gama de la matriz):

foo(x, s) { 
    sumBelow = 0; 
    lower = 0; 
    upper = x.size(); 
    while (lower + 1 != upper) { 
    mid = (upper + lower)/2; 
    partition(x, lower, mid, upper); // O(upper - lower) time 
    sumb = 0; 
    maxb = 0; // assuming non-negative to avoid use of flags 
    for (i = lower; i < mid; i++) { 
     sumb += x[i]; 
     maxb = max(maxb, x[i]); 
    } 
    if (sumBelow + sumb + maxb * (x.size() - mid) <= s) { 
     lower = mid; 
     sumBelow += sumb; 
    } else { 
     upper = mid; 
    } 
    } 
    K = (s - sumBelow)/(x.size() - lower); 
    if (K > maxElement(x)) return error(); 
    else return K; 
} 

Answer 5

tipo que nlogn

int[] sortedArray; 
int s; 

int sum=0; 

for(int i=0; i<sortedArray.length; i++){ 
    sum = sum + sortedArray[i]; 

    if((s - sum)/(sortedArray.length - i) < sortedArray[i+1]){ 
    return (s - sum)/(sortedArray.length - i); 
    } 
} 

Answer 6

Bueno parece que llego tarde, pero de todas formas espero que este algoritmo tiene algún sentido.

1. Primero divide S con el tamaño de la matriz. Obtendrás 42.
2. Encuentra cuántos números en la matriz son mayores que 42, aquí es 2 (P).
3. Agregue todos los números menores que 42 y encuentre N = 210 - (suma de números menores que 42).

4. Al final N/P debería darle la respuesta perfecta y está en O (N) Complejidad del tiempo y O (1) Complejidad del espacio.

   encontrar el código de ejecución aquí: http://ideone.com/MDL3iy

   import java.util.Scanner; 
   class Ideone { 
   
   public static void main(String args[]) { 
   Scanner in = new Scanner(System.in); 
   int S = in.nextInt(); 
   int[] array = {90,30,100,40,20}; 
   int len = array.length; 
   int sAvg = S/len; 
   
   int trackSmallerThanAverage = 0; 
   int countMorethanAverage = 0; 
   
   for(int i=0; i<len; i++) { 
       if(array[i] > sAvg) { 
        countMorethanAverage ++; 
       } else if (array[i]<sAvg) { 
        trackSmallerThanAverage += array[i]; 
        } 
   
       } 
   
       int finalValue = (S - trackSmallerThanAverage)/countMorethanAverage; 
       System.out.println(finalValue); 
       in.close(); 
   
   } 
   }