Wybierz liczbę m z tablicy n liczb, więc ich całkowita różnica jest minimalna.

Question

Istnieje n wież ze zmienną liczbą pięter w starożytnym mieście. Musimy na nich budować podłogi, aby co najmniej m z n wież (n> = m) było równej wysokości. Napisz funkcję obliczającą minimalną liczbę pięter, które muszą zostać zbudowane, aby m podłogi były równej wysokości.

Przykład: Biorąc pod uwagę tablicę (1,5,4,2,1), każdy element reprezentujący liczbę pięter w tej wieży i m = 3, funkcja powinna wrócić 2, ponieważ musimy zbudować 1 piętro dla każdej z wież na indeksie 0 & 4, więc 3 wieże będą równej wysokości. Definicja funkcji poniżej:

public Integer calcMinFloors(Integer[] towers, int m); 

Answer 1

Sortuje się według wzrostu w porządku rosnącym lub malejącym, a reszta jest banalna.

Answer 2

Problem ten jest rozpuszczalny czas O (NlogN) i stały odstęp O (1) gdzie N jest ilość wież.

Musimy wykonać wieże o takiej samej wysokości, aby zbudować podłogi minimum.

Ważne Obserwacje

. Ponieważ budujemy minimalne podłogi, a nie budujemy pięter na wieżach i osiągamy jednakową wysokość, postaramy się, aby wieże o wysokości równej wysokości wieży docelowej były wykonane.

. Optymalne rozwiązanie polega na znalezieniu takich m wieże, które mają minimalny suma wysokości difference.Let Rozwiązaniem okazać wieże posiadające następujące piętra w rosnącym:

m1 , m2 , m3 , ....... m floor 

optymalne rozwiązanie ma następującą właściwość:

suma różnic jest minimalna:

(m - m1) + (m - m2) + (m - m3) + .....(m - (m-1)) 

bo tylko wtedy możemy powiedzieć, że musimy zbuduj minimalną liczbę pięter.

Tak więc okazało się, że musimy znaleźć zestaw m podłogi tak, że różnica ich wysokości od podłogi z maksymalną wysokością (w obrębie tych wież) wynosi minimum.

Powiedzmy, że mamy tablicę arr o długości n, przedstawiająca liczbę pięter na każdej wieży. Najpierw mamy wieże o wysokości.

Następnie zaczynamy znajdować sumę differences w następujący sposób. Powiedzmy, że jesteśmy w index i w. Znajdujemy następującą kwotę:

arr[i + m - 1] - arr[i] 
     + 
arr[i + m - 2] - arr[i] 
     + 
arr[i + m - 3] - arr[i] 
     + 
arr[i + m - 4] - arr[i] 
     . 
     . 
     . 
arr[i + 1] - arr[i] 

Pozwala wywołać sumę s1.Teraz, gdy weźmiemy pod uwagę kolejny zestaw m wież, czyli wieże z indeksów i + 1 do i + m, nie potrzebują pętli obliczyć sumę różnic, to może być po prostu pochodzić z następujących:

(m - 1)*arr[i + m] - s1 - ((m-1)*arr[i]) 

Tak używając tej prostej techniki matematycznej, potrzebujemy tylko jednej pętli for tego problemu.

pseudokod dla proponowanego algorytmu jest:

Sort the array arr of n towers. 

Compute the sum of differences for first set of m towers. 

sum = 0 

for(i = 1 to m - 1) 
{ 
    sum = sum + arr[i] - arr[0] 
} 

Now for the remaining set of m towers 

previous_sum = sum, sum = 0, j = 1 
minimum_sum = previous_sum 
for(i = m to n - 1) 
{ 

sum = (m-1)*arr[i] - previous_sum - (m - 1)*arr[j - 1] 
increment j 

if(sum < minimum_sum) 
{ 
    minimum_sum = sum 
} 

previous_sum = sum 
} 

The answer is minimum_sum. 

Answer 3

Aktualizacja odpowiedź od @ gnasher729:

proste rozwiązanie dla n elementu tablicy:

1. sortowane w porządku malejącym: (5,4,2,1,1)
2. Pętla nad elementami i dla każdego elementu spójrz w przyszłość m-1 następne elementy. Zsumuj różnice i zaoszczędź minimum. Czas złożoność O(n*m)

Nieco bardziej zaawansowane rozwiązanie:

1. Sortuj w porządku malejącym: (5,4,2,1,1)
2. Get pierwszy element (5), patrzeć w przyszłość m-1 elementy (4,2), ilu podłogi trzeba (1 + 3 = 4) i zapisać wynik jako best i jako current
3. Przeprowadź pętlę nad tablicą z elementu 2. dla każdego elementu i obliczyć wartość: current = current - (arr[i-1] - arr[i])*(m-1) + arr[i]-arr[i+m-1]. Zaoszczędź na best, jeśli jest mniejszy.

To powinno dać złożoność czasu O(n*log(n)) do sortowania + O(n) dla kroków 2-3.