Вот накидал с достаточно подробными, для того чтобы разобраться самому, комментариями программу, которая работает без сортировки за линейное время. Идея в том, чтобы проходя однократно по массиву поддерживать акутальными текущие три минимальные числа, обновляя их с учетом каждого последующего элемента массива. Это решение легко расширяется на поиск любого фиксированного числа N минимальных элементов, не только трех.
P.S. Для ArrayList с алгоритмической точки зрения все делается точно так же. Я написал, как мне проще и быстрее, чтобы объяснить суть решения, а не конкретную техническую реализацию.
class Test {
// Здесь будут храниться наши три минимальные числа.
static int min[] = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
// Обновляем массив `min` имея новое число-кандидат в минимум.
static void updateMin(int x) {
// Перебираем текущие минимальные числа.
for (int i = 0; i < 3; ++i) {
if (x < min[i]) {
// Новое число меньше рассматриваемого из `min`.
// Сдвигаем текущее и последующие числа, чтобы освободить место
// для нового.
for (int j = 2; j > i; --j)
min[j] = min[j - 1];
// Вставляем новое число на полагающееся ему место.
min[i] = x;
// Дело сделано.
return;
} else if (x == min[i]) {
// Новое число равно рассматриваемому из `min`.
// Заканчиваем, т.к. такое число уже есть среди минимальных.
return;
}
// Иначе переходим к следующему числу из `min`
}
}
public static void main(String[] args) {
int loc[] = {25, 11, 250, 5, 45, 8, 10, 45, 31, 123, 489};
// Находим три минимальных числа.
for (int i = 0; i < loc.length; ++i)
updateMin(loc[i]);
// Выводим их
// (проверка на MAX_VALUE на случай, если минимальных чисел окажется
// меньше трех).
for (int i = 0; i < 3 && min[i] != Integer.MAX_VALUE; ++i)
System.out.println(min[i]);
}
}
|
0 / 0 / 0 Регистрация: 26.06.2021 Сообщений: 18 |
|
|
1 |
|
Найти три наименьших элемента массива и переставить их в начало01.06.2022, 18:13. Показов 981. Ответов 13
Напишите программу, которая находит три наименьших элемента массива и переставляет их в начало массива. Остальные элементы должны следовать далее в том же порядке. Не могу понять, как решить эту задачу. Буду очень благодарен, если подскажете, как она решается.
0 |
|
JIupToH 32 / 20 / 13 Регистрация: 20.05.2022 Сообщений: 333 |
||||
|
01.06.2022, 22:54 |
2 |
|||
0 |
|
0 / 0 / 0 Регистрация: 26.06.2021 Сообщений: 18 |
|
|
02.06.2022, 21:29 [ТС] |
3 |
|
Не работает ваш код.
0 |
|
32 / 20 / 13 Регистрация: 20.05.2022 Сообщений: 333 |
|
|
02.06.2022, 21:43 |
4 |
|
AlexPoronov, почему?
0 |
|
2340 / 1868 / 606 Регистрация: 29.06.2020 Сообщений: 7,056 |
|
|
02.06.2022, 21:50 |
5 |
|
Не работает ваш код. Да, он кривоват, я делал, суть та же , но работает стабильно.
0 |
|
32 / 20 / 13 Регистрация: 20.05.2022 Сообщений: 333 |
|
|
02.06.2022, 21:52 |
6 |
|
СКриншот программы…
0 |
|
32 / 20 / 13 Регистрация: 20.05.2022 Сообщений: 333 |
|
|
02.06.2022, 21:55 |
7 |
|
SmallEvil, интересно, что именно кривовато…. Нет предела совершенства, просто это первое, что на ум пришло)) Добавлено через 2 минуты
0 |
|
SmallEvil 2340 / 1868 / 606 Регистрация: 29.06.2020 Сообщений: 7,056 |
||||
|
02.06.2022, 22:01 |
8 |
|||
|
Не работает ваш код.
почему? вектор:
вывод: 1 1 1 5 1 8 2 1 Видно что элементов ‘1’ стало 5, вместо 4, Добавлено через 1 минуту
SmallEvil, интересно, что именно кривовато…. Нет предела совершенства, просто это первое, что на ум пришло)) С подходом все норм, я пытался придумать эффективнее, не вышло.
0 |
|
32 / 20 / 13 Регистрация: 20.05.2022 Сообщений: 333 |
|
|
02.06.2022, 22:27 |
9 |
|
SmallEvil, тогда повторяющиеся элементы надо удалять…. просто иначе странно будет, что 1 единицы в начале. А интересно, почему у меня так получилось…
0 |
|
1703 / 1103 / 337 Регистрация: 25.01.2019 Сообщений: 2,901 |
|
|
02.06.2022, 22:28 |
10 |
|
тогда повторяющиеся элементы надо удалять С какого перепугу?
0 |
|
JIupToH 32 / 20 / 13 Регистрация: 20.05.2022 Сообщений: 333 |
||||
|
02.06.2022, 22:41 |
11 |
|||
|
SmallEvil, условие изменить надо, и тогда в начале будут единицы и двойка не затирается))
0 |
|
SmallEvil 2340 / 1868 / 606 Регистрация: 29.06.2020 Сообщений: 7,056 |
||||
|
02.06.2022, 22:47 |
12 |
|||
|
Решение
А интересно, почему у меня так получилось… Не знаю, все эти +1 и -1 с индексами, часто выходят боком…. Решение в лоб. Кликните здесь для просмотра всего текста
Но что то мне это не нравится … Добавлено через 3 минуты
условие изменить надо, и тогда в начале будут единицы и двойка не затирается)) ага, только потерался строй Код 1 1 1 1 2 5 8 2 Но в задании не указано ничего про про выбор минимальных чисел …
1 |
Сообщение было отмечено AlexPoronov как решение
|
32 / 20 / 13 Регистрация: 20.05.2022 Сообщений: 333 |
|
|
02.06.2022, 23:04 |
13 |
|
SmallEvil, так всмысле потерялся строй, если элемент наименьший то он идет в начало. все правильно) Добавлено через 5 минут
0 |
|
2340 / 1868 / 606 Регистрация: 29.06.2020 Сообщений: 7,056 |
|
|
02.06.2022, 23:04 |
14 |
|
Но что то мне это не нравится … Итого, в широком смысле, где размер вектора может быть большим, так же как и N (наименьших элементов для обработки),
0 |
Переделаем на Паскаль:
var Min1, Min2, Min3: Double
var n: Integer, A(32767): Double, i: Integer
‘ Запрашиваем размер массива
Readln(n);
‘ Формируем массив
for i := 1 To n do
Writeln (“Введите ” & i & “-ый член массива”);
Readln (A(i));
‘ Сначала ищем самое наименьшее число
Min1 := A(1);
for i := 2 To n do
If A(i) < Min1 Then Min1 := A(i);
‘ Теперь ищем второе наименьшее число, которое больше первого, но меньше всех остальных
Min2 := A(1)
for i := 2 To n do
If (A(i) < Min2) AND (A(i) > Min1) Then Min2 := A(i);
‘ А теперь третье, которое больше второго, но меньше всех остальных
Min3 := A(1)
for i := 2 To n do
If (A(i) < Min3) AND (A(i) > Min2) Then Min3 := A(i);
‘ И выводим все три числа
Writeln (Min1, Min2, Min3)
End
Дима почему-то пишет конкретное число в 10000000, но не учитывает, что числа могут быть все больше него, и тогда его код не сработает, потому что x(i) так и останется 10000000.
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Find the first, second and third minimum elements in an array in O(n).
Examples:
Input : 9 4 12 6
Output : First min = 4
Second min = 6
Third min = 9
Input : 4 9 1 32 12
Output : First min = 1
Second min = 4
Third min = 9
First approach : First we can use normal method that is sort the array and then print first, second and third element of the array. Time complexity of this solution is O(n Log n).
C++
#include<bits/stdc++.h>
using namespace std;
int Print3Smallest(int array[], int n)
{
sort(array,array+n);
cout << "First min = " << array[0] << "n";
cout << "Second min = " << array[1] << "n";
cout << "Third min = " << array[2] << "n";
}
int main()
{
int array[] = {4, 9, 1, 32, 12};
int n = sizeof(array) / sizeof(array[0]);
Print3Smallest(array, n);
return 0;
}
Java
import java.util.Arrays;
public class Main {
static void Print3Smallest(int array[], int n) {
Arrays.sort(array);
System.out.println("First min = " + array[0]);
System.out.println("Second min = " + array[1]);
System.out.println("Third min = " + array[2]);
}
public static void main(String[] args) {
int array[] = {4, 9, 1, 32, 12};
int n = array.length;
Print3Smallest(array, n);
}
}
Python3
def print_3_smallest(array):
array.sort()
print("First min =", array[0])
print("Second min =", array[1])
print("Third min =", array[2])
if __name__ == '__main__':
array = [4, 9, 1, 32, 12]
n = len(array)
print_3_smallest(array)
C#
using System;
using System.Linq;
class Program
{
static void Print3Smallest(int[] array, int n)
{
Array.Sort(array);
Console.WriteLine("First min = " + array[0]);
Console.WriteLine("Second min = " + array[1]);
Console.WriteLine("Third min = " + array[2]);
}
static void Main()
{
int[] array = {4, 9, 1, 32, 12};
int n = array.Length;
Print3Smallest(array, n);
}
}
Javascript
function Print3Smallest(array,n){
array.sort((a, b) => a - b);
console.log('First min = ' + array[0]);
console.log('Second min = ' + array[1]);
console.log('Third min = ' + array[2]);
}
let array = [4, 9, 1, 32, 12];
Print3Smallest(array,array.length);
Output
First min = 1 Second min = 4 Third min = 9
Second approach : Time complexity of this solution is O(n).
Algorithm:
- First take an element
- then if array[index] < Firstelement
- Thirdelement = Secondelement
- Secondelement = Firstelement
- Firstelement = array[index]
- else if array[index] < Secondelement
- Thirdelement = Secondelement
- Secondelement = array[index]
- else if array[index] < Thirdelement
- Thirdelement = array[index]
- then print all the element
Implementation:
C++
#include<bits/stdc++.h>
#define MAX 100000
using namespace std;
int Print3Smallest(int array[], int n)
{
int firstmin = MAX, secmin = MAX, thirdmin = MAX;
for (int i = 0; i < n; i++)
{
if (array[i] < firstmin)
{
thirdmin = secmin;
secmin = firstmin;
firstmin = array[i];
}
else if (array[i] < secmin)
{
thirdmin = secmin;
secmin = array[i];
}
else if (array[i] < thirdmin)
thirdmin = array[i];
}
cout << "First min = " << firstmin << "n";
cout << "Second min = " << secmin << "n";
cout << "Third min = " << thirdmin << "n";
}
int main()
{
int array[] = {4, 9, 1, 32, 12};
int n = sizeof(array) / sizeof(array[0]);
Print3Smallest(array, n);
return 0;
}
Java
import java.util.*;
public class GFG
{
static void Print3Smallest(int array[], int n)
{
int firstmin = Integer.MAX_VALUE;
int secmin = Integer.MAX_VALUE;
int thirdmin = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
{
if (array[i] < firstmin)
{
thirdmin = secmin;
secmin = firstmin;
firstmin = array[i];
}
else if (array[i] < secmin)
{
thirdmin = secmin;
secmin = array[i];
}
else if (array[i] < thirdmin)
thirdmin = array[i];
}
System.out.println("First min = " + firstmin );
System.out.println("Second min = " + secmin );
System.out.println("Third min = " + thirdmin );
}
public static void main(String[] args)
{
int array[] = {4, 9, 1, 32, 12};
int n = array.length;
Print3Smallest(array, n);
}
}
Python3
MAX = 100000
def Print3Smallest(arr, n):
firstmin = MAX
secmin = MAX
thirdmin = MAX
for i in range(0, n):
if arr[i] < firstmin:
thirdmin = secmin
secmin = firstmin
firstmin = arr[i]
elif arr[i] < secmin:
thirdmin = secmin
secmin = arr[i]
elif arr[i] < thirdmin:
thirdmin = arr[i]
print("First min = ", firstmin)
print("Second min = ", secmin)
print("Third min = ", thirdmin)
arr = [4, 9, 1, 32, 12]
n = len(arr)
Print3Smallest(arr, n)
C#
using System;
class GFG
{
static void Print3Smallest(int []array, int n)
{
int firstmin = int.MaxValue;
int secmin = int.MaxValue;
int thirdmin = int.MaxValue;
for (int i = 0; i < n; i++)
{
if (array[i] < firstmin)
{
thirdmin = secmin;
secmin = firstmin;
firstmin = array[i];
}
else if (array[i] < secmin)
{
thirdmin = secmin;
secmin = array[i];
}
else if (array[i] < thirdmin)
thirdmin = array[i];
}
Console.WriteLine("First min = " + firstmin );
Console.WriteLine("Second min = " + secmin );
Console.WriteLine("Third min = " + thirdmin );
}
static void Main()
{
int []array = new int[]{4, 9, 1, 32, 12};
int n = array.Length;
Print3Smallest(array, n);
}
}
PHP
<?php
function Print3Smallest($array, $n)
{
$MAX = 100000;
$firstmin = $MAX;
$secmin = $MAX;
$thirdmin = $MAX;
for ($i = 0; $i < $n; $i++)
{
if ($array[$i] < $firstmin)
{
$thirdmin = $secmin;
$secmin = $firstmin;
$firstmin = $array[$i];
}
else if ($array[$i] < $secmin)
{
$thirdmin = $secmin;
$secmin = $array[$i];
}
else if ($array[$i] < $thirdmin)
$thirdmin = $array[$i];
}
echo "First min = ".$firstmin."n";
echo "Second min = ".$secmin."n";
echo "Third min = ".$thirdmin."n";
}
$array= array(4, 9, 1, 32, 12);
$n = sizeof($array) / sizeof($array[0]);
Print3Smallest($array, $n);
?>
Javascript
<script>
let MAX = 100000
function Print3Smallest( array, n)
{
let firstmin = MAX, secmin = MAX, thirdmin = MAX;
for (let i = 0; i < n; i++)
{
if (array[i] < firstmin)
{
thirdmin = secmin;
secmin = firstmin;
firstmin = array[i];
}
else if (array[i] < secmin)
{
thirdmin = secmin;
secmin = array[i];
}
else if (array[i] < thirdmin)
thirdmin = array[i];
}
document.write("First min = " + firstmin + "</br>");
document.write("Second min = " + secmin + "</br>");
document.write("Third min = " + thirdmin + "</br>");
}
let array = [4, 9, 1, 32, 12];
let n = array.length;
Print3Smallest(array, n);
</script>
Output
First min = 1 Second min = 4 Third min = 9
Time Complexity: O(n)
Auxiliary Space: O(1)
Last Updated :
09 Mar, 2023
Like Article
Save Article
Найти первый, второй и третий минимальные элементы в массиве
30.12.2019Массивы, Поиск, Школьное программирование
Найти первый, второй и третий минимальные элементы в массиве в O (n).
Примеры:
Input : 9 4 12 6
Output : First min = 4
Second min = 6
Third min = 9
Input : 4 9 1 32 12
Output : First min = 1
Second min = 4
Third min = 9
Первый подход : сначала мы можем использовать обычный метод, который сортирует массив, а затем печатать первый, второй и третий элемент массива. Временная сложность этого решения составляет O (n Log n).
Второй подход : временная сложность этого решения O (n).
Алгоритм-
First take an element
then if array[index] < Firstelement
Thirdelement = Secondelement
Secondelement = Firstelement
Firstelement = array[index]
else if array[index] < Secondelement
Thirdelement = Secondelement
Secondelement = array[index]
else if array[index] < Thirdelement
Thirdelement = array[index]
then print all the element
C ++
#include<iostream>
#define MAX 100000
using namespace std;
int Print3Smallest(int array[], int n)
{
int firstmin = MAX, secmin = MAX, thirdmin = MAX;
for (int i = 0; i < n; i++)
{
if (array[i] < firstmin)
{
thirdmin = secmin;
secmin = firstmin;
firstmin = array[i];
}
else if (array[i] < secmin)
{
thirdmin = secmin;
secmin = array[i];
}
else if (array[i] < thirdmin)
thirdmin = array[i];
}
cout << "First min = " << firstmin << "n";
cout << "Second min = " << secmin << "n";
cout << "Third min = " << thirdmin << "n";
}
int main()
{
int array[] = {4, 9, 1, 32, 12};
int n = sizeof(array) / sizeof(array[0]);
Print3Smallest(array, n);
return 0;
}
Джава
import java.util.*;
public class GFG
{
static void Print3Smallest(int array[], int n)
{
int firstmin = Integer.MAX_VALUE;
int secmin = Integer.MAX_VALUE;
int thirdmin = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
{
if (array[i] < firstmin)
{
thirdmin = secmin;
secmin = firstmin;
firstmin = array[i];
}
else if (array[i] < secmin)
{
thirdmin = secmin;
secmin = array[i];
}
else if (array[i] < thirdmin)
thirdmin = array[i];
}
System.out.println("First min = " + firstmin );
System.out.println("Second min = " + secmin );
System.out.println("Third min = " + thirdmin );
}
public static void main(String[] args)
{
int array[] = {4, 9, 1, 32, 12};
int n = array.length;
Print3Smallest(array, n);
}
}
python3
MAX = 100000
def Print3Smallest(arr, n):
firstmin = MAX
secmin = MAX
thirdmin = MAX
for i in range(0, n):
if arr[i] < firstmin:
thirdmin = secmin
secmin = firstmin
firstmin = arr[i]
elif arr[i] < secmin:
thirdmin = secmin
secmin = arr[i]
elif arr[i] < thirdmin:
thirdmin = arr[i]
print("First min = ", firstmin)
print("Second min = ", secmin)
print("Third min = ", thirdmin)
arr = [4, 9, 1, 32, 12]
n = len(arr)
Print3Smallest(arr, n)
C #
using System;
class GFG
{
static void Print3Smallest(int []array, int n)
{
int firstmin = int.MaxValue;
int secmin = int.MaxValue;
int thirdmin = int.MaxValue;
for (int i = 0; i < n; i++)
{
if (array[i] < firstmin)
{
thirdmin = secmin;
secmin = firstmin;
firstmin = array[i];
}
else if (array[i] < secmin)
{
thirdmin = secmin;
secmin = array[i];
}
else if (array[i] < thirdmin)
thirdmin = array[i];
}
Console.WriteLine("First min = " + firstmin );
Console.WriteLine("Second min = " + secmin );
Console.WriteLine("Third min = " + thirdmin );
}
static void Main()
{
int []array = new int[]{4, 9, 1, 32, 12};
int n = array.Length;
Print3Smallest(array, n);
}
}
PHP
<?php
function Print3Smallest($array, $n)
{
$MAX = 100000;
$firstmin = $MAX;
$secmin = $MAX;
$thirdmin = $MAX;
for ($i = 0; $i < $n; $i++)
{
if ($array[$i] < $firstmin)
{
$thirdmin = $secmin;
$secmin = $firstmin;
$firstmin = $array[$i];
}
else if ($array[$i] < $secmin)
{
$thirdmin = $secmin;
$secmin = $array[$i];
}
else if ($array[$i] < $thirdmin)
$thirdmin = $array[$i];
}
echo "First min = ".$firstmin."n";
echo "Second min = ".$secmin."n";
echo "Third min = ".$thirdmin."n";
}
$array= array(4, 9, 1, 32, 12);
$n = sizeof($array) / sizeof($array[0]);
Print3Smallest($array, $n);
?>
Выход:
First min = 1 Second min = 4 Third min = 9
Рекомендуемые посты:
- Найдите минимальное значение, чтобы назначить все элементы массива, чтобы произведение массива стало больше
- Найти минимальные изменения, необходимые в массиве, чтобы он содержал k различных элементов
- Рекурсивные программы для поиска минимальных и максимальных элементов массива
- Найдите минимальное количество элементов, которые должны быть удалены, чтобы сделать массив хорошим
- Найти минимальное количество операций, необходимых для выравнивания всех элементов массива
- Отразите минимальные знаки элементов массива, чтобы получить минимально возможную сумму положительных элементов
- Найти исходный массив из зашифрованного массива (массив сумм других элементов)
- Найти элементы больше, чем половина элементов в массиве
- Сумма всех минимально встречающихся элементов в массиве
- Минимальное значение среди AND элементов каждого подмножества массива
- Удалите минимальные элементы из массива так, чтобы max <= 2 * min
- Удалите минимальные элементы из массива, так что 2 * min станет больше, чем max
- Найти минимальную разницу между любыми двумя элементами
- Найти минимальные элементы после рассмотрения всех возможных преобразований
- Найдите минимальную сумму, такую, чтобы был взят один из каждых трех последовательных элементов
Найти первый, второй и третий минимальные элементы в массиве
0.00 (0%) 0 votes
