Finden größte und zweitgrößte Elements in einem Bereich
https://stackoverflow.com/questions/1412751
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie finde ich die oben ohne das größte Element zu entfernen und die Suche wieder? Gibt es eine effizientere Art und Weise, dies zu tun? Dabei spielt es keine Rolle, ob die diese Elemente sind Duplikate.
Lösung
for (e: all elements) {
if (e > largest) {
second = largest;
largest = e;
} else if (e > second) {
second = e;
}
}
Sie könnten entweder initialisieren largest und second auf eine geeignete untere Grenze, oder auf die ersten beiden Elemente in der Liste (überprüfen, welche größer ist, und vergessen Sie nicht, zu überprüfen, ob die Liste mindestens zwei Elemente hat)
Andere Tipps
std::partial_sort(aTest.begin(), aTest.begin() + 2, aTest.end(), Functor);
Ein Beispiel:
std::vector<int> aTest;
aTest.push_back(3);
aTest.push_back(2);
aTest.push_back(4);
aTest.push_back(1);
std::partial_sort(aTest.begin(), aTest.begin()+2,aTest.end(), std::greater<int>());
int Max = aTest[0];
int SecMax = aTest[1];
nth_element(begin, begin+n,end,Compare) legt das Element, das n-te sein würde (wobei „erste“ ist „0-te“), wenn der Bereich [begin, end) an Position begin+n sortiert wurden und stellt sicher, dass alles von [begin,begin+n) vor dem n-ten Element in der sortierten Liste erscheinen würde. So ist der Code, den Sie wollen, ist:
nth_element(container.begin(),
container.begin()+1,
container.end(),
appropriateCompare);
Das funktioniert gut in Ihrem Fall, da Sie nur sind die beiden größten suchen. Angenommen, Ihre appropriateCompare sortiert Dinge vom größten zum kleinsten, mit dem zweitgrößten Element an Position 1 sein und die größten in der Position sein wird, 0
Nehmen wir an, Sie meinen die beiden größten eindeutige Werte in der Liste zu finden.
Wenn die Liste bereits sortiert ist, dann schauen Sie in dem zweiten letzten Elemente (oder besser gesagt, vom Ende iterieren für vorletzter Wert suchen).
Wenn die Liste unsortiert ist, dann nicht die Mühe, es zu sortieren. Die Sortierung erfolgt am besten O (n lg n). Einfache lineare Iteration ist O (n), so dass nur eine Schleife über die Elemente zu verfolgen:
v::value_type second_best = 0, best = 0;
for(v::const_iterator i=v.begin(); i!=v.end(); ++i)
if(*i > best) {
second_best = best;
best = *i;
} else if(*i > second_best) {
second_best = *i;
}
Es gibt natürlich auch andere Kriterien, und diese alle in den Test innerhalb der Schleife genommen werden können. Sie sollten jedoch bedeuten, dass zwei Elemente, die beide den gleichen größten Wert haben sollte gefunden werden, müssen Sie überlegen, was sollten Elemente mit drei oder mehr passiert, alle haben diesen größten Wert, oder wenn zwei oder mehr Elemente haben die zweitgrößte.
Der optimale Algorithmus sollte nicht mehr benötigen als 1,5 * N - 2 Vergleiche. (Einmal haben wir uns entschieden, dass es O (n), was vor N der Koeffizient ist? 2 * N Vergleiche sind weniger als optimal).
Also, zuerst die „Gewinner“ bestimmen und die „Verlierer“ in jedem Paar - das sind 0,5 * N Vergleiche
.Dann das größte Element bestimmen Gewinner zu vergleichen - das ist eine andere 0,5 * N -. 1 Vergleiche
Dann bestimmt das zweitgrößte Element durch den Verlierer des Paars zu vergleichen, wo das größte Element aus gegen die Gewinner aller anderen Paare kam - weiteren 0,5 * N -. 1 Vergleich
Insgesamt Vergleiche = 1,5 N -. 2
Die Antwort hängt, wenn Sie nur die Werte wollen, oder auch Iteratoren auf den Werten zeigen.
Minor Modifikation von @will Antwort.
v::value_type second_best = 0, best = 0;
for(v::const_iterator i=v.begin(); i!=v.end(); ++i)
{
if(*i > best)
{
second_best = best;
best = *i;
}
else if (*i > second_best)
{
second_best = *i;
}
}
Erstellen Sie eine Unterliste von n..m, absteigend sortieren sie. Dann greifen die ersten beiden Elemente. Löschen Sie diese Elemente aus der ursprünglichen Liste.
Sie können die Liste in einem Durchgang scannen und die 1. und 2. Werte speichern, die eine O (n) Effizienz hat beim Sortieren O (n log n) ist.
EDIT:
Ich denke, dass eine partielle Art ist O (n log k)
Nicht getestet, aber Spaß:
template <typename T, int n>
class top_n_functor : public unary_function<T, void>
{
void operator() (const T& x) {
auto f = lower_bound(values_.begin(), values_.end(), x);
if(values_.size() < n) {
values_.insert(f, x);
return;
}
if(values_.begin() == f)
return;
auto removed = values_.begin();
values_.splice(removed, values_, removed+1, f);
*removed = x;
}
std::list<T> values() {
return values_;
}
private:
std::list<T> values_;
};
int main()
{
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
auto vals = for_each(A, A + N, top_n_functor<int,2>()).values();
cout << "The top is " << vals.front()
<< " with second place being " << *(vals.begin()+1) << endl;
}
Wenn das größte ist das erste Element, wenn nach dem zweitgrößten in [größten + 1, Ende). Such Ansonsten in [beginnen, am größten) und [größten + 1, Ende) und das Maximum der zwei nehmen. Natürlich hat diese O (2n), so optimal ist es nicht.
Wenn Sie Random-Access-Iteratoren haben, könnten Sie so schnell Art zu tun hat und nutzen die immer elegant Rekursion:
template< typename T >
std::pair<T,T> find_two_largest(const std::pair<T,T>& lhs, const std::pair<T,T>& rhs)
{
// implementation finding the two largest of the four values left as an exercise :)
}
template< typename RAIter >
std::pair< typename std::iterator_traits<RAIter>::value_type
, typename std::iterator_traits<RAIter>::value_type >
find_two_largest(RAIter begin, RAIter end)
{
const ptr_diff_t diff = end-begin;
if( diff < 2 )
return std::make_pair(*begin, *begin);
if( diff < 3 )
return std::make_pair(*begin, *begin+1);
const RAIter middle = begin + (diff)/2;
typedef std::pair< typename std::iterator_traits<RAIter>::value_type
, typename std::iterator_traits<RAIter>::value_type >
result_t;
const result_t left = find_two_largest(begin,middle);
const result_t right = find_two_largest(middle,end);
return find_two_largest(left,right);
}
Das hat O (n) und soll nicht mehr Vergleiche machen als nomen Implementierung .
Top-k ist in der Regel ein bisschen besser als n (log k)
template <class t,class ordering>
class TopK {
public:
typedef std::multiset<t,ordering,special_allocator> BEST_t;
BEST_t best;
const size_t K;
TopK(const size_t k)
: K(k){
}
const BEST_t& insert(const t& item){
if(best.size()<k){
best.insert(item);
return best;
}
//k items in multiset now
//and here is why its better - because if the distribution is random then
//this and comparison above are usually the comparisons that is done;
if(compare(*best.begin(),item){//item better than worst
erase(begin());//the worst
best.insert(item); //log k-1 average as only k-1 items in best
}
return best;
}
template <class it>
const BEST_t& insert(it i,const it last){
for(;i!=last;++i){
insert(*i);
}
return best;
}
};
Natürlich kann die special_allocator im Wesentlichen sein nur ein Array von k multiset value_types und eine Liste dieser Knoten (die in der Regel nichts über sie als die anderen k sind im Einsatz in der multiset bis zu seiner Zeit einen neuen zu setzen in und wir löschen und dann sofort ly wiederverwenden. Gut, dies zu haben oder aber der Speicher alloc / frei in std :: multiset und der Cache-Zeile Mist tötet ya. es ist ein (sehr) klein bisschen Arbeit zu geben, ihm statischen Zustand ohne Verletzung STL Allocator Regeln.
Nicht so gut wie ein spezialisiertes algo für genau 2 aber für festen k<<n, würde ich GUESS (2n + Delta * n), wobei Delta ist klein - mein DEK ACP vol3 S & S ist weggepackt und eine Schätzung auf Delta ist ein bisschen mehr Arbeit, die ich tun möchte.
Durchschnitt Schlimmste ist, ich würde vermuten, n (log (k-1) + 2), wenn in umgekehrter Reihenfolge und alle verschieden.
am besten ist 2n + k (log k) für die k am besten, die erste zu sein
