Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.12.2018, 21:36   #1
mirvam
Форумчанин
 
Регистрация: 03.08.2018
Сообщений: 129
По умолчанию Поиск двух максимальных элементов массива

Нужно найти два максимальных элемента массива за одно прохождение О(n), и учесть нюанс, когда первый элемент может быть максимальным.
Как решить задачу?
Пока такая мысль (рабочая, но не О(n))
Код:
var task = [345, 865, 387, 286, 983, 276, 687, 234, 918, 631, 397, 463, 928, 285, 469];
var results = [];
var max = task[0];

for (var n = 0; n < task.length; n++) {
  if (task[n] > max) {
    max = task[n];
  }
}
results.push([max, task.indexOf(max)]);

max = task[1];
for (var n = 0; n < task.length; n++) {
  if (task[n] > max) {
    if (n !== results[0][1]) {
      max = task[n];
    }
  }
}
results.push([max, task.indexOf(max)]);

alert(results[0][0] + " " + results[1][0]);
mirvam вне форума Ответить с цитированием
Старый 19.12.2018, 22:13   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

как то задача непонятно звучит..
что такое
Цитата:
Сообщение от mirvam Посмотреть сообщение
два максимальных элемента массива
?

пусть дан массив:
1 1 1 1 1 1
какие два "максимальных элемента" ?

пусть дан массив:
100 1 100 1 100 1
какие два "максимальных элемента" ?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 20.12.2018, 11:21   #3
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,537
По умолчанию

По-моему, непонятки нет: не спрашивают об индексах макс. элементов, а только величины - макс. и следующий за ним <= макс. В первом случае - 1,1 , во вторм - 100,100.
На Паскале это звучало бы вроде так:
Код:
const N = ......
var Max_first, Max_second,i : integer ; my_arr: array [1.. N] of integer ;
if my_arr[1] > my_arr[2] then 
   begin
       Max_first := my_arr[1] ;  Max_second := my_arr[2] end
else 
     begin
       Max_first := my_arr[2] ;  Max_second := my_arr[1] end ;
for i := 3 to N do
   if  my_arr[i] >  Max_first  then
      begin Max_second :=  Max_first ;  Max_first := my_arr[i] end
   else  if my_arr[i] >  Max_second  then Max_second :=   my_arr[i] ;
digitalis вне форума Ответить с цитированием
Старый 09.01.2019, 17:03   #4
Алексей_2012_
Подтвердите свой е-майл
 
Регистрация: 09.01.2019
Сообщений: 3
По умолчанию

digitalis, на втором тесте алгоритм завалился, решил переписать на JS, вроде выдержаны все тонкости реализации)

Проще отсортировать массив по возрастанию и вывести 2 последних элемента в отсортированном массиве. Вроде где-то находил алгоритм с одним проходом во время сортировки.


Код:
<html>
<head>
<meta charset="windows-1251">
<title>два максимума</title>
</head>

<script>
	
	//Наполнение массива с клавиатуры
	function inputArr(count)	
	{	
		var arr=[];
		if (count<=0) count=1;
		do
		{
			arr.push(+prompt('Введите элемент, осталось ввести — '+count,'5'));	
			count--;
		}
		while(count>=1);
	return arr.join('*'); //возвращение строки введенных элементов 
	}

	function twoMax(arr_str)
	{
		var _arr = arr_str.split('*');
		var t1, t2;

		if (_arr[0]>_arr[1]) 
		{
			t1=_arr[0];
			t2=_arr[1];
		} else {
		
			t1=_arr[1];
			t2=_arr[0];
		}
			
		

		for (var i=2;i<_arr.length;i++)
		{
			if (_arr[i]>t1) 
			{
				t2=t1; 
				t1=_arr[i];
			}	else 
				if (_arr[i]>t2) t2=_arr[i];
		}
		
		return 'Общая последовательность: '+_arr.join(' ')+'; Max1 = '+t1+'; Max2 = '+t2;		

	}

	alert(twoMax(inputArr(+prompt('Введите количество чисел в последовательности...',10))));

</script>


<body>
 <p> Hello </p>
</body>
</html>
Изображения
Тип файла: jpg скрин.jpg (37.4 Кб, 132 просмотров)
Алексей_2012_ вне форума Ответить с цитированием
Старый 09.01.2019, 17:50   #5
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,537
По умолчанию

Приведенный пример - видимо, массив был воспринят компилятором как short int - тогда конечно, первое число получилось как бы отрицательным. JS - тут я не копенгаген. Алгоритм работает правильно, никто никуда завалился.

5465465 243 6 76 87878
5465465 87878

Насчет сортировки... Можно, конечно, ехать из Москвы в Тамбов через СПб, но через Рязань, думаю, ближе.

Последний раз редактировалось digitalis; 09.01.2019 в 18:20.
digitalis вне форума Ответить с цитированием
Старый 09.01.2019, 17:57   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

В тесте может быть для прикола N=1 )
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 09.01.2019, 20:30   #7
Байтик
Пользователь
 
Регистрация: 21.12.2018
Сообщений: 28
По умолчанию

Цитата:
Сообщение от Алексей_2012_ Посмотреть сообщение
отсортировать массив по возрастанию
Это никак не O(n)
Байтик вне форума Ответить с цитированием
Старый 09.01.2019, 20:36   #8
Байтик
Пользователь
 
Регистрация: 21.12.2018
Сообщений: 28
По умолчанию

Однако, вынужден извиниться. Если есть много дополнительной памяти, то все, конечно, возможно. Хотя бы хэш-алгоритмами.
Байтик вне форума Ответить с цитированием
Старый 10.01.2019, 02:59   #9
Алексей_2012_
Подтвердите свой е-майл
 
Регистрация: 09.01.2019
Сообщений: 3
По умолчанию

В JS, как таковых, типов shortint нету, нашел ошибку, JS думал что массив - это string, добавил преобразование в число и все заработало как надо)

После C++ и Delphi на JS прогать не удобно
Алексей_2012_ вне форума Ответить с цитированием
Старый 10.01.2019, 18:46   #10
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,656
По умолчанию

Код:
#define INT_MIN -2147483648
typedef struct { int first, second; } TMaxRec;

TMaxRec foo(int* x, unsigned count)
{
  TMaxRec mr = {INT_MIN, INT_MIN};

  // единственный цикл
  for (unsigned idx = 0; idx != count; idx++)
  {
    if (x[idx] > mr.second)
      mr.second = x[idx];

    if (x[idx] > mr.first)
    {
      mr.second = mr.first;
      mr.first = x[idx];
    }
  } // for

  return mr;
}
000384.png
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
min@y™ вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
При однократном просмотре целочисленного массива X найти два максимальных числа Xmax1 и Xmax2 соответственно среди четных и нечетных по значению элементов массива Anonim123321 Общие вопросы C/C++ 11 11.12.2017 11:08
[Delphi]: Сортировка массива, состоящего из максимальных элементов заданных матриц hozer Помощь студентам 2 05.12.2016 23:32
C# Массив. Сумма двух элементов массива. Skipper Ok Помощь студентам 3 15.09.2014 08:19
Определение максимальных элементов массива (С++) Johnny_Grunge Помощь студентам 4 21.01.2012 16:28
поиск максимальных элементов в массиве radiokarazinec Общие вопросы Delphi 1 26.12.2010 12:53