Как вычислить 2 наименьших нечетных элемента массива в языке С?

Question

[ugh_newbie_ugh]

Как вычислить 2 наименьших нечетных элемента массива в языке С?

Comments

[Антон Воскобоев]

Обратиться на фриланс.

Answer 1

[Wataru]

Решайте задачу по частям. Сначала выведите все нечетные элементы в массиве.

Потом (отдельно) найдите в массиве 2 наименьших элемента.

Потом совместите 2 алгоритма.

Answer 2

[LoliDeveloper]

Так?

int Arr[] = {.......};
int min1 = (2<<31) -1, min2 = (2<<31) -1;
for(int i = 0; i < size; ++i)
{
     if(min1 % 2 == 1 && Arr[i] < min1)
          min1 = Arr[i];
     else if(min2 % 2 == 1 && Arr[i] < min2)
          min2 = Arr[i];
}

Comments

[soloveid]

Нет, за один проход ты точно не решишь задачу

[LoliDeveloper]

soloveid, Да прям, почему это?

[soloveid]

int *arr;
int min1Index = 0;
int min1 = arr[0];

int min2 = arr[0];
for(int i = 0; i < size; ++i)
{
    if(arr[i] < min1 && arr[i] % 2 == 1)
    {
        min1 = arr[i];
        min1Index = i;
    }
}

for(int i = 0; i < size; ++i)
{
    if(i != min1Index  && arr[i] < min2 &&  arr[i] % 2 == 1)
        min2 = arr[i];
}

Как-то так, если эти два значения могут быть одинаковы.

[soloveid]

LoliDeveloper, не зная самый минимальный Вы не можете найти второй после минимального.
Чтобы найти самый минимальный надо пройти весь массив в любом случае.
Итого получаем, что надо минимум два цикла (второй цикл чтобы найти второй минимальный)

[LoliDeveloper]

soloveid, так у меня первый min1 меньше второго всегда, а поскольку там else if, а не else, то случай с двумя одинаковыми min1 == min2 будет корректен, нам же главное 2 разных элемента, а не числа

[LoliDeveloper]

soloveid, всё что больше или равно первого минимального будет падать во второй минимальный

[soloveid]

В условии задачи не написано что там надо разное:
разные позиции этих элементов или
разные значения этих элементов.
Второе получается просто изменением условия во втором цикле.

Нужно уточнение у автора, наверное автор сам толком не знает.

[LoliDeveloper]

soloveid, В любом случае это решается в один проход.
Просто добавить условие Arr[i] != min1

[soloveid]

LoliDeveloper,

soloveid, всё что больше или равно первого минимального будет падать во второй минимальный

Да, так и делал. Надо два разных значения, то надо просто поменять условие во втором цикле на

if(arr[i] != min1 && arr[i] < min2 &&  arr[i] % 2 == 1)

[soloveid]

LoliDeveloper,

В любом случае это решается в один проход.

Напиши свой код и я приведу тебе пример на котором он не работает,
или извинюсь и признаю свою неправоту.

[LoliDeveloper]

если надо 2 разных числа, то

int Arr[] = {.......};  //гарантируется что там есть минимум 2 разных числа. 
                             //Если нет, то можно добавить флаги
int min1 = (2<<31) -1, min2 = (2<<31) -1;
for(int i = 0; i < size; ++i)
{
     if(min1 % 2 == 1 && Arr[i] < min1)
          min1 = Arr[i];
     else if(min2 % 2 == 1 && Arr[i] < min2 && Arr[i] != min1)
          min2 = Arr[i];
}

[soloveid]

Ну вот тебе массив, на котором это банально не работает
{3, 1}
Всё, больше не хочу продолжать с тобой общение.

[LoliDeveloper]

soloveid, Господи, тут же интуитивно понятно что в 2 прохода это смерть. Я не силён писать без отладки, но этот код потестил

int Arr[] = { 1,1231,23123,1234,35,452356,564563,7345,235345,2345363,4523452342,3};  //гарантируется что там есть минимум 2 разных числа. 
							 //Если нет, то можно добавить флаги
	int min1 = (2 << 30) - 1, min2 = (2 << 30) - 1; // изначально очень большие числа 
	for (int i = 0; i < 12; ++i)
	{
		if (min1 % 2 == 1 && Arr[i] < min1)
		{
			min2 = min1;
			min1 = Arr[i];
			continue;
		}
		if (min2 % 2 == 1 && Arr[i] < min2 && Arr[i] != min1)
		{
			min2 = Arr[i];
		}

	}

[Wataru]

не зная самый минимальный Вы не можете найти второй после минимального.

soloveid, Можно решить и за один проход. Достаточно поддерживать минимальный и второй минимальный элементы. Потом каждый новый элемент может вытеснить или второй минимальный, или самый минимальный (при этом вытесненное значение вытесняет второй минимальный). Грубо говоря добавляете новый элемент к текущим двум минимальным и выкидываете худший из трех. Сокращается до 2 условий:

if (a[i] < min1) {
  min2 = min1;
  min1 = a[i];
} else if (a[i] < min2) {
  min2 = a[i];
}

Если нужны именно разные значения, то надо добавить условие во второй if.

понятно что в 2 прохода это смерть.

LoliDeveloper, Один проход, 2 прохода - разницы практически нет. Экономите только инкремент индекса и условие конца цикла. А тела циклов можно хоть вместе, хоть последовательно выполнять - от перестановки слагаемых сумма не меняется.

Раз вам эта задача не кажется очевидной, советую 2 прохода, таки использовать.

[soloveid]

Wataru,

Можно решить и за один проход

Да, можно, согласен.