Хитрый вопрос Интервью по поиску

Question

Я недавно услышал этот вопрос от друга, которого спросили об этом в интервью. Он не смог понять это, и я пока не нашел эффективного решения. Я надеюсь, что здесь есть алгоритмист, который может показать мне новый подход

Вопрос:

Учитывая массив A и число S ', предоставьте эффективный алгоритм (nlogn), чтобы найти число K, такое, что если все элементы в A больше K будут заменены на K, сумма всех элементов в результирующем массиве будет быть S '.

Например, для A: [90,30,100,40,20] и S' = 210, K будет 60.

Answer 1

Написано на Python, которое должно быть достаточно читабельным, даже если вы не знаете язык:

#!/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

Результат:

60

Сортировка - O ( n log n ), а цикл - O ( n ). Таким образом, объединенный алгоритм в целом равен O ( n log n ).

Answer 2

Сначала отсортируйте список от наименьшего к наибольшему и определите его длину.Затем начните складывать числа по одному.На каждом шаге также найдите нижний предел для того, какой может быть сумма - какой будет сумма всего списка, если все остальные числа, которые вы еще не добавили, совпадают с текущим числом.

В какой-то момент этот нижний предел суммы изменится от меньшего, чем S ', к большему, чем S', и в этот момент вы можете сделать некоторую арифметику, чтобы определить, какой должна быть отсечка.Например (C = текущая сумма, L = нижний предел общей суммы):

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

C2 = 20 + 30 = 50
L2 = 50 + 3*30 = 140 &lt 210

C3 = 50 + 40 = 90
L3 = 90 + 2*40 = 170 &lt 210

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

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

Answer 3

Это может быть выполнено без сортировки по времени O (n) с использованием изменения линейного времени, выбранного следующим образом (обратите внимание, что время выполнения итераций цикла while образует геометрический ряд - подпрограмма разделения разделяет диапазонмассива, от нижнего к верхнему, на элементы, меньшие или большие, чем элемент ранга mid, а время выполнения пропорционально размеру диапазона массива):

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 4

Ну, похоже, я опоздал, но в любом случае надеюсь, что этот алгоритм имеет какой-то смысл.

1. Сначала разделите S на размер массива.Вы получите 42.
2. Найдите, сколько чисел в массиве больше 42, здесь это 2 (P).
3. Добавьте все числа меньше 42 и найдите N = 210 -(сумма чисел меньше 42).

4. В конце N / P должен дать вам идеальный ответ, и он в O (N) сложности времени и O (1) сложности пространства.

   Найдите код выполнения здесь: 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();
   
   }
   }
   

Answer 5

Вот мое решение.Я в основном делаю бинарный поиск значения K в диапазоне [0, max (A)].Хотя это избавляет от необходимости сначала сортировать массив (сохраняя, таким образом, исходный массив), это все равно O (n * log (k)), где n - количество элементов в A, а k - максимальное значение в 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 6

сортируй 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);
  }
}