Третье по величине число в массиве?
можете ли вы сказать мне, как найти третье по величине число в массиве?
без заказа
спасибо за ответы
Лично я бы их упорядочил: сортировка в порядке убывания сделала бы это тривиальной проблемой.
Но если вы не можете использовать сортировку, то это домашнее задание. Так что вы не получите код!
Но это не сложно.
Подумайте об этом: как бы вы нашли максимальное значение?
Ответ: цикл, хотя все записи в массиве сравниваются друг с другом по текущему значению. Если это значение больше текущего, то оно становится новым максимумом.
Это довольно простой вопрос, чтобы сделать это найти тройку лучших: когда вы замените максимум, переместить его во второй по величине, а второй в третий. Один проход, готово.
Хорошее предложение. 5!
Привет, Оригиналгрифф.
При всем моем сочувствии к вашему решению, я думаю, что оно не совсем правильно. Единственный цикл для нахождения максимума, конечно, прекрасно работает; но обобщение для трех лучших немного сложнее. Рассмотрим следующую последовательность действий:
1 5 10 7 6
Когда вы достигнете 10, три верхних массива будут содержать (10, 5, 1). При встрече с 7 вы выбрасываете его, так как он не больше текущего максимума. То же самое с 6. Таким образом, ваш алгоритм приведет к тому, что 10, 5, 1 будут первыми тремя.
Таким образом, вы фактически должны сравнивать каждый новый элемент со всеми членами в верхней тройке массива или пока не найдете тот, который меньше.
Хорошая мысль! Отчасти поэтому я бы сначала их сортировал...
Хорошо подмечено - я бы дал вам 5, если бы мог. Так что я нашел один из твоих ответов и нашел... :)
Это было очень любезно с вашей стороны, спасибо! На самом деле этот алгоритм занял бы почти 3N сравнений, в то время как хороший алгоритм сортировки занял бы только немного больше (в порядке N ln N). Следовательно, ваше чувство было правильным, что делать вид-не самая худшая идея в мире.
Интересно, есть ли алгоритм, который делает гораздо лучше, чем 3N, чтобы найти первую тройку. Если я найду что-нибудь существенное, я свяжусь с вами, ребята.
Большое преимущество выполнения сортировки заключается в том, что она сокращает тестирование - если это не критичный по времени раздел кода, то я бы выбрал версию сортировки исключительно во время разработки!
Я абсолютно согласен. Я бы тоже так поступил.
Просто ради того, чтобы придумать решение, которое не использует обычную сортировку, вот что я бы сделал:
Мы используем стек из трех ячеек для хранения наших трех лучших кандидатов, которые мы нашли до сих пор. Назовем их A, B и C, причем C - наименьшее значение. Теперь сделайте цикл над массивом и сравните каждый новый элемент X сначала с C, нашим самым низким из трех лучших. Если он больше, замените C на X. Затем сравните его с В. Если он больше, нажмите B вниз в C и установите B В X. Затем повторите это для А.
Таким образом, во многих случаях нам сойдет с рук только одно сравнение, а именно X с C. Это происходит потому, что через некоторое время относительно большие значения будут накоплены в A, B, C, и поэтому большинство элементов, которые мы сравниваем, будут ниже, чем C.
Это более экономично, чем начинать сравнение с X до A, затем B и, наконец, C.
Все это говорит о том, что это не что иное, как выполнение старой доброй вставки, за исключением того, что мы выбрасываем все, что находится ниже трех верхних элементов.
Я надеюсь, что эта информация придет вовремя для Амира-Мар2012.
Если вы не можете упорядочить массив по каким-либо причинам, вы всегда можете создать дополнительный индекс, который будет просто отражать порядок, а затем использовать этот индекс для поиска нужного элемента.
//Возьмите три переменные и назначьте первый элемент массива, а затем
проверьте на самый большой номер. Если найдено, то переместите первое нет во вторую переменную и так далее в третью переменную.
int[] arr = {1,8,4,5,12,2,5,6,7,1,90,100,56,8,34};
int temp, f, s, t;
f = s = t = arr[0];
foreach (int i in arr)
{
if (f < i)
{
temp = f;
f = i;
s = temp;
}
if (s < i && f > i)
{
temp = i;
s = i;
t = temp;
}
if (t < i && s > i)
{
temp = i;
t=i;
}
}
MessageBox.Show(t.ToString());