العثور على أكبر وثاني أكبر عنصر في النطاق

Question

كيف يمكنني العثور على ما سبق دون إزالة العنصر الأكبر والبحث مرة أخرى؟هل هناك طريقة أكثر فعالية للقيام بذلك؟ولا يهم إذا كانت هذه العناصر مكررة.

Answer 1

for (e: all elements) {
 if (e > largest) {
   second = largest;
   largest = e;
 } else if (e > second) {
   second = e;
 }
}

وأنت إما أن تهيئة largest وsecond إلى أقل من المناسب ملزمة، أو إلى البندين الأولين في القائمة (تحقق واحد الذي هو أكبر، و لا تنسى للتحقق مما إذا قائمة اثنين على الأقل سلعة)

Answer 2

partial_sort ؟

std::partial_sort(aTest.begin(), aTest.begin() + 2, aTest.end(), Functor);

مثال:

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];

Answer 3

وnth_element(begin, begin+n,end,Compare) يضع العنصر الذي سيكون نطة (حيث "أولا" هو "0") إذا تم فرز [begin, end) مجموعة في موقف begin+n ويتأكد أن كل شيء من [begin,begin+n) سوف تظهر قبل العنصر الألف في القائمة التي تم فرزها. لذلك الرمز الذي تريده هو:

nth_element(container.begin(),
            container.begin()+1,
            container.end(),
            appropriateCompare);

وهذا سوف تعمل بشكل جيد في قضيتك، منذ كنت تبحث فقط لاثنين أكبر. على افتراض appropriateCompare الخاص بفرز الأشياء من الأكبر إلى الأصغر، ثاني أكبر عنصر مع أن يكون في الموضع 1 والأكبر سيكون في موقف 0.

Answer 4

لنفترض تقصد للعثور على اثنين من أكبر القيم الفريدة في القائمة.

إذا يتم فرز القائمة بالفعل، ثم مجرد إلقاء نظرة على الثاني على العنصر الأخير (أو بالأحرى، أعاد من نهاية تبحث عن الثانية القيمة الأخيرة).

إذا تم فرزها القائمة، ثم لا تهتم لترتيب هذا الامر. الفرز هو في أحسن الأحوال O (ن إل جي ن). التكرار الخطي البسيط هو O (ن)، حتى مجرد حلقة على عناصر تتبع:

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;
   }

وهناك بالطبع معايير أخرى، وهذه يمكن أن تكون كلها وضعت في اختبار داخل الحلقة. ومع ذلك، يجب أن يعني أن اثنين من العناصر التي لديهما يجب جدت نفسها أكبر قيمة، لديك للنظر في ما يحدث يجب أن ثلاثة أو أكثر من العناصر جميعا هذا أكبر قيمة، أو إذا اثنين أو أكثر من العناصر لديها ثاني أكبر.

Answer 5

والخوارزمية المثلى يجب أن لا تحتاج إلى أكثر من 1.5 * N - 2 المقارنات. (مرة واحدة قررنا أنه O (ن)، ما هو معامل أمام N؟ 2 * N مقارنات أقل من المستوى الأمثل).

وهكذا، أولا تحديد "الفائز" و "الخاسر" في كل زوج - هذا هو 0.5 * مقارنات N

.

وبعد ذلك تحديد أكبر عنصر بمقارنة الفائزين - وهذا 0.5 * N آخر - 1 مقارنات

وثم تحديد عنصر ثاني أكبر بمقارنة الخاسر من الزوج حيث جاء أكبر عنصر من أمام الفائز من كل الأزواج الأخرى - 0.5 * N آخر - 1 مقارنات

ومجموع مقارنات = 1.5 N - 2

Answer 6

والجواب يتوقف إذا كنت ترغب فقط في القيم، أو أيضا المكررات مشيرا في القيم.

وتعديل طفيف للإجابةwill.

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;
   }
}

Answer 7

وإنشاء قائمة فرعية من n..m، نوع ذلك تنازلي. ثم الاستيلاء على العنصرين الأولين. حذف هذه العناصر من القائمة أصلي.

Answer 8

ويمكنك مسح القائمة في مرور واحد وحفظ 1 والقيم 2ND، التي لديها O (ن) كفاءة في حين الفرز هو O (ن سجل ن).

وتحرير:
وأعتقد أن هذا النوع الجزئي O (ن تسجيل ك)

Answer 9

وغير مختبر ولكن متعة:

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;
}

Answer 10

إذا الأكبر هو العنصر الأول، ابحث عن ثاني أكبر سوق في [أكبر + 1، النهاية). وإلا بحث في [تبدأ، أكبر) و [أكبر + 1، نهاية)، واتخاذ أقصى من الاثنين. وبطبيعة الحال، وهذا له O (2N)، حتى انها ليست الأمثل.

إذا كان لديك المكررات الوصول العشوائي، هل يمكن أن تفعل الفرز كما سريعة لا واستخدام العودية-أنيقة من أي وقت مضى:

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);
}

وهذا له O (ن) وينبغي ألا بذل المزيد من المقارنات من <لأ href = "https://stackoverflow.com/questions/1412751/find-largest-and-second-largest-element-in-a- مجموعة / 1412792 # 1412792 "> NomeN في تنفيذ .

Answer 11

عادةً ما يكون أعلى k أفضل قليلاً من 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;
    }
  };

بالطبع special_allocator يمكن أن يكون في جوهره مجرد مصفوفة من أنواع قيم k متعددة المجموعات وقائمة بتلك العقد (والتي لا تحتوي عادةً على أي شيء لأن k الأخرى قيد الاستخدام في المجموعة المتعددة حتى يحين وقت وضع عقدة جديدة ونمسحها ثم نمسحها على الفور إعادة استخدامه.من الجيد أن يكون لديك هذا وإلا فإن تخصيص الذاكرة/مجاني في std::multiset وحماقة خط ذاكرة التخزين المؤقت تقتلك.إنه عمل صغير (جدًا) لمنحه حالة ثابتة دون انتهاك قواعد تخصيص STL.

ليست جيدة مثل الخوارزمية المتخصصة لشخصين بالضبط ولكنها ثابتة k<<n, ، أود أن أخمن (2n+delta*n) حيث تكون الدلتا صغيرة - تم تعبئة DEK ACP vol3 S&S الخاص بي وتقدير الدلتا هو عمل إضافي أريد القيام به.

المتوسط ​​الأسوأ هو أنني أعتقد أن n(log(k-1) + 2) عندما تكون بترتيب معاكس وكلها متميزة.

الأفضل هو 2n + k(log k) لأن k الأفضل هو الأول