Самое эффективное решение

← →
Rwer (2006-10-16 16:28) [0]

Как решить такую простую задачку самым эффективным способом:
Дан массив чисел, выбрать 3 наибольших.
1 самый тупой способ: осортировать массив вывести 3 последних элемента.
2 способ: три раза проходить по массиву и вычислять минимальное значение.

А как можно это реализовать самым лучшим способом?

← →
Alien1769 © (2006-10-16 16:33) [1]

функция екселя тебе поможет :))

← →
Johnmen © (2006-10-16 16:35) [2]

> выбрать 3 наибольших.

> вычислять минимальное значение.

>

Те.е минимальное значение называется "наибольшее"? :)))

3 один раз пройти по массиву, определяя святую троицу чисел...

← →
Sandman29 © (2006-10-16 16:35) [3]

3) решить задачу в лоб. то есть пройтись один раз и запоминать 3 наибольших.

← →
Alien1769 © (2006-10-16 16:38) [4]

> и запоминать 3 наибольших.

чисел без знака.

← →
palva © (2006-10-16 16:39) [5]

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

← →
Jeer © (2006-10-16 16:41) [6]

зависит от выбранного способа сортировки и размера массива.
т.е. для первого и второго случаев существует некоторая "цена" операции.
Если отобразить на графике зависимость от N для этих двух случаев, то при нелинейном характере одной из операций возможно пересечение графиков в точке, где "цена" одинакова.

Для второго случая ориентировочно "цена" == 3*K*N, т.е. линейная зависимость.

← →
TUser © (2006-10-16 17:44) [7]

Сотворить стек из трех элементов и пихать туда. Пример
procedure Up (var S: TStack; N: integer); begin with S do begin if N < length (Vects) - 1 then with Vects[N] do SetInStack (S, N+1, FileName, Atom, VLen); end; end; procedure Push (var Stack: TStack; Name, Atm: string; Len: cardinal); var i: integer; f: boolean; begin with Stack do begin i := Count-1; if Count < MaxCount then GrowStack (Stack); f := true; while f and (i >= 0) do if Vects[i].VLen > Len then begin Up (Stack, i); dec (i); end else f := false; if (not f) or (i < 0) then if i < MaxCount - 1 then SetInStack (Stack, i+1, Name, Atm, Len); end; end; procedure PushStruct (S: TStructure); var i: integer; begin with S do for i := 0 to MolCount-1 do with Molecules[i] do Push (MyStack, FileName, Line, Sums[NVector-1]); end;

← →
Ketmar © (2006-10-16 18:06) [8]

сделать SQL-таблицу, всё занести, потом выбрать %-)

← →
oldman © (2006-10-16 18:57) [9]

а почему способ 1 "самый тупой", если задача сводится к поиску 3 максимумов???
или это я "самый тупой"?

← →
TUser © (2006-10-16 19:01) [10]

> oldman © (16.10.06 18:57) [9]

Ясно, что [7] быстрее.

← →
oldman © (2006-10-16 19:04) [11]

> TUser © (16.10.06 19:01) [10]

Писать дольше.
И думать больше.

← →
default © (2006-10-16 19:33) [12]

2 способ вполне и вполне
по крайней мере для немалых массивов я пути лучше не вижу

← →
default © (2006-10-16 20:23) [13]

возможный способ реализации 2 способа
public static int[] GetThreeMaxInt(int[] arr) { if (arr == null) throw new ArgumentNullException(); if (arr.Length < 3) throw new ArgumentOutOfRangeException("argument must be >= 3"); int max; int[] res = new int[3]; int[] ind = new int[3]; for (int i = 0; i < 3; i++) { ind[2-i] = i; max = arr[i]; for (int j = i+1; j < arr.Length; j++) { if (arr[j] > max) { ind[2-i] = j; max = arr[j]; } } res[2-i] = max; arr[ind[2-i]] = Int32.MinValue; } for (int i = 0; i < 3; i++) arr[ind[i]] = res[i]; return res; } static void Main(string[] args) { foreach (int el in GetThreeMaxInt(new int[] {4, 8, 10, 2, 1, 16, 19})) Console.WriteLine(el); }

← →
Rwer (2006-10-16 22:12) [14]

> procedure Up (var S: TStack; N: integer);begin with S do
> begin if N < length (Vects) - 1 then with Vects[N]
> do SetInStack (S, N+1, FileName, Atom, VLen); end;
> end;procedure Push (var Stack: TStack; Name, Atm: string;
> Len: cardinal);var i: integer; f: boolean;begin with
> Stack do begin i := Count-1; if Count < MaxCount then
> GrowStack (Stack); f := true; while f and (i
> >= 0) do if Vects[i].VLen > Len then begin Up
> (Stack, i); dec (i); end else f := false;
> if (not f) or (i < 0) then if i < MaxCount - 1 then
> SetInStack (Stack, i+1, Name, Atm, Len); end;end;
> procedure PushStruct (S: TStructure);var i: integer;begin
> with S do for i := 0 to MolCount-1 do with Molecules[i]
> do Push (MyStack, FileName, Line, Sums[NVector-1]);
> end;

А покороче нельзя 3 числа найти никак??
Я вот подумал... что лучший способ это пройти один раз по массиву и выбрать эти три числа. А как реализовать?
может, например так:

max1:=-MaxInt; max2:=max1; max3:=max;
for i:=1 to n do begin
if a[i]>max1 then max1:=a[i];
if (a[i]>max2) and (a[i]<max1) then max2:=a[i];
if (a[i]>max3) and (a[i]<max2) then max3:=a[i];
end;

Ну что скажете? Предложите свои варианты!

← →
Rwer (2006-10-16 22:15) [15]

Вот мудрость:
Настоящий программист никогда не делает всё хорошо с первого раза, он понимает важность патчей

← →
homm © (2006-10-16 22:35) [16]

>
> max1:=-MaxInt; max2:=max1; max3:=max;
> for i:=1 to n do begin
> if a[i]>max1 then max1:=a[i];
> if (a[i]>max2) and (a[i]<max1) then max2:=a[i];
> if (a[i]>max3) and (a[i]<max2) then max3:=a[i];
> end;

на вскидку: из последовательности
182838 вернет 832

← →
default © (2006-10-16 22:45) [17]

я же дал код
public static int[] GetThreeMaxInt(int[] arr) { if (arr == null) throw new ArgumentNullException(); if (arr.Length < 3) throw new ArgumentOutOfRangeException("argument must be >= 3"); int[] max = new int[3]; int[] ind = new int[3]; for (int i = 0; i < 3; i++) { max[2-i] = arr[0]; ind[2-i] = 0; for (int j = 1; j < arr.Length; j++) { if (arr[j] > max[2-i]) { ind[2-i] = j; max[2-i] = arr[j]; } } arr[ind[2-i]] = Int32.MinValue; } for (int i = 0; i < 3; i++) arr[ind[i]] = max[i]; return max; }
p.s. в предыдущем была ошибка писал на скорую руку

← →
homm © (2006-10-16 22:49) [18]

> Rwer (16.10.06 16:28)

> Как решить такую простую задачку самым эффективным способом:

> [17] default © (16.10.06 22:45)

> for (int i = 0; i < 3; i++)
> {
> max[2-i] = arr[0];
> ind[2-i] = 0;
> for (int j = 1; j < arr.Length; j++) {
> if (arr[j] > max[2-i])
> {
> ind[2-i] = j;
> max[2-i] = arr[j];
> }
> }
> arr[ind[2-i]] = Int32.MinValue;
> }

что-то мне не кажется что одно с другим карелирует.

homm © (16.10.06 22:49) [18]
найди способ эффективнее
если делять за один проход, то быстрее не будет только мороки больше

default © (16.10.06 23:10) [19]

Если значение меньше третьего, то получится всего одно сравнение. То есть для трехпроходного метода K=3, а для третьего метода K чуть больше 1.

var a,b,c,i: Integer; begin a := -MaxInt; b := -MaxInt; c := -MaxInt; for i := 0 to High(Arr) do if Arr[i] > с then if Arr[i] > b then begin c := b; if Arr[i] > a then begin b := a; a := Arr[i]; end else b := Arr[i]; end else c := Arr[i]; end;
Ну плюс проверки разные, если охота. :)

Sandman29 © (17.10.06 09:15) [20]
да, таки побыстрее будет
я почему-то на сравнения только ориентировался(присваивания не брал)
а по сравнениям способ 2 чуть получше чем [21] в его худшем случае
поэтому я и подумал что игра не стоит свеч:)

> 2 способ вполне и вполне по крайней мере для немалых массивов я пути лучше не вижу

Опять же см. [7]. Там требуется один проход по массиву + n проходов по вспомогательному массиму длины 3.

Ну, впрочем, не нравится, - ходите три раза.

Jeer © (17.10.06 13:54) [24]
да, для него такой массив не подарок
но он и при таком не пасует за счёт меньшего числа присваиваний

Пасует перед стеком в простейшей его форме:

procedure Search_02;
var i: integer;
begin
for i := 0 to High(Arr) do begin
if (Arr[i] > a) then begin
c := b;
b := a;
a := Arr[i];
end
else
if (Arr[i] > b) then begin
c := b;
b := Arr[i];
end
else
if Arr[i] > c then c := Arr[i];
end;
end;

Самое эффективное решение Найти похожие ветки