hvernig á að finna næstminnstu töluna í fylki


svara 1:

fyrst verður þú að tilgreina þvinganir þínar.

geri ráð fyrir að þú verðir að gera þetta í O (nlogn)

raðaðu einfaldlega fylkinu eða vektorinum og fáðu niðurstöðuna þína.

ef þú verður að gera það O (N)

þá skaltu einfaldlega skanna fylkið eða vigurinn og finna minnsta frumefnið. skanna aftur fylkið eða vigurinn til að finna minnsta frumefnið sem er stærra en finndu fyrst minnsta frumefni.

þetta mun taka O (n) + O (n) sem er jafnt og O (n) en krefst tveggja skanna.

en ef þú verður að gera það á skilvirkari hátt og tölurnar eru af handahófi þá geturðu fundið þættina í einni skönnun þ.e O (n).

# innifalið að nota namespace std;aðal aðal (){int smallest_first = INT_MAX, smallest_second = INT_MAX, n;cin >> n;vektor vec (n);fyrir (int i = 0; icin >> vec [i];ef (n <2){cout << "þú verður að hafa tvo þætti \ n";skila 0;} fyrir (int i = 0; i { if (vec [i] { smallest_second = minnsta_fyrsta; minnsti_ fyrsti = vec [i]; } annað ef (vec [i] minnsta_sekúnda = vec [i]; }cout <skila 0;}

Vona að þetta hjálpi.


svara 2:

Það eru margar leiðir sem þú getur notað til að leysa þetta vandamál.

AÐFERÐ 1 - Þú getur raðað fylkinu og skilað frumefninu sem er til staðar við 0 og 1 vísitölu fylkis.

Tímaflækjan í þessari nálgun er O (nlogn). En mikilvægt atriði er að þessi aðferð virkar ekki ef um endurtekna þætti er að ræða.

AÐFERÐ 2- Við getum leyst þetta vandamál í einni braut með því að taka tvær breytur (minnstu og næstminnstu).

Fara yfir fylki og gera skilyrt eftirlit -

a) Ef núverandi þáttur er minni en minnstur, uppfærðu þá minnstu.

b) Annars ef núverandi þáttur er stærri en minnstur og minni en næstminnstur, uppfærðu næstminnsta.

Tímaflækjustig þessarar nálgunar er O (n).

opinber truflanir int getSecondSmallest (int arr []) { int smallest = Heiltala.MAX_VALUE; int secondSmallest = Heiltala.MAX_VALUE; // Fara yfir fylki fyrir (int i = 0; i ef (arr [i] minnsti = arr [i]; } ef (arr [i]> minnsti && arr [i] secondSmallest = arr [i]; } } skila öðruMinni }Finndu næstminnstu töluna í fylki: Java kóða

svara 3:

Ef fylkið er óflokkað, hafðu tvær breytur 'fyrsta' og 'annað' og haltu áfram að endurtekna í gegnum fylkið og haltu áfram að breyta breytunum með því að bera saman við hvern þátt.

Dæmi um kóða:

fyrir (int i: input) {if (i> fyrst) {second = first; fyrst = i; } annað ef (i> annað) annað = i; }

Ef þú vilt finna nth minnsta eða stærsta þáttinn geturðu notað valreiknirit

http://en.m.wikipedia.org/wiki/Selection_algorithm

Ef fylki er flokkað geturðu fengið það á stöðugum tíma.


svara 4:

Þú getur gert það á 2 vegu.

1. Flokkaðu fylkið og 1. og annar þáttur væri svar þitt.

2. Taktu tvo var min1 og min2

Reiknirit:

mín1 = Heiltala.MAX_VALUE

mín2 = Heiltala.MAX_VALUE

fyrir (int i = 0; i

ef (a [i]

min2 = min1;

min1 = a [i];

}

}

Athugið: ef n <2 þá verður aðeins einn lágmarksþáttur.

Ef n == 2 þá geturðu notað Math.min (a, b);