범위에서 가장 크고 두 번째로 큰 요소를 찾으십시오

StackOverflow https://stackoverflow.com/questions/1412751

문제

가장 큰 요소를 제거하고 다시 검색하지 않고 위의 것을 어떻게 찾습니까? 더 효율적인 방법이 있습니까? 이러한 요소가 복제인지는 중요하지 않습니다.

도움이 되었습니까?

해결책 

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

초기화 할 수 있습니다 largest 그리고 second 적절한 하한 또는 목록의 첫 두 항목에 (어느 쪽이 더 큰지 확인하고 목록에 두 개 이상의 항목이 있는지 확인하는 것을 잊지 마십시오)

다른 팁

사용 partial_sort ?

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

An Example:

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) 범위 인 경우 요소가 nth ( "첫 번째"인 경우 "0th")를 배치합니다. [begin, end) 위치에서 분류되었습니다 begin+n 그리고 모든 것을 확인합니다 [begin,begin+n) 정렬 된 목록의 N 번째 요소 앞에 나타납니다. 그래서 당신이 원하는 코드는 다음과 같습니다.

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

당신은 가장 큰 두 가지만 찾고 있기 때문에 이것은 당신의 경우에 잘 작동합니다. 당신의 적절한 공동체가 가장 큰 것부터 가장 작은 것까지, 두 번째로 큰 요소는 위치 1에 있고 가장 큰 요소는 위치 0에 있습니다.

목록에서 가장 큰 두 가지 고유 한 값을 찾는 것을 의미한다고 가정 해 봅시다.

목록이 이미 정렬 된 경우 두 번째 마지막 요소를보십시오 (또는 두 번째 마지막 값을 찾는 끝에서 반복).

목록이 분류되지 않은 경우 정렬하지 마십시오. 정렬은 기껏해야 O (n lg n)입니다. 간단한 선형 반복은 O (n)이므로 추적을 유지하는 요소를 통해 반복합니다.

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

물론 다른 기준이 있으며, 이들은 모두 루프 내부의 테스트에 참여할 수 있습니다. 그러나 두 가지 값이 가장 큰 두 요소를 찾아야한다는 것을 의미한다면, 3 개 이상의 요소 가이 값이 가장 큰 값을 가지거나 두 개 이상의 요소가 두 번째로 큰 경우 발생하는 일을 고려해야합니다.

최적의 알고리즘은 1.5 * n -2 비교가 필요하지 않아야합니다. (우리가 O (n)이라고 결정한 후에는 n? 2 * n 앞에있는 계수는 무엇입니까?

따라서 먼저 각 쌍의 "승리"와 "패자"를 결정하십시오. 이는 0.5 * N 비교입니다.

그런 다음 승자를 비교하여 가장 큰 요소를 결정하십시오. 또 다른 0.5 * N -1 비교입니다.

그런 다음 가장 큰 요소가 다른 모든 쌍의 우승자와 비교 한 쌍의 패자를 비교하여 두 번째로 큰 요소를 결정하십시오 - 또 다른 0.5 * n -1 비교.

총 비교 = 1.5 n -2.

대답은 값을 원하거나 값을 가리키는 반복자를 원하는지 여부에 따라 다릅니다.

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

n..m에서 Subrist를 만들고 내림차순을 정렬하십시오. 그런 다음 처음 두 요소를 잡으십시오. 원 기관 목록에서 이러한 요소를 삭제하십시오.

한 번의 패스로 목록을 스캔하고 정렬이 O (n log n) 인 동안 O (n) 효율을 갖는 첫 번째 및 두 번째 값을 저장할 수 있습니다.

편집하다:
나는 부분 정렬이 O (n log k)라고 생각합니다.

테스트되지 않았지만 재미 :

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

가장 큰 것이 첫 번째 요소 인 경우 [가장 큰+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 (n)을 가지고 있으며 Nomen의 구현.

상단 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 multiset value_types의 배열 일 뿐이고 해당 노드 목록이 될 수 있습니다 (일반적으로 다른 k가 멀티 세트에 새 제품을 넣을 때까지 사용되지 않기 때문에 아무것도 없습니다. 재사용하십시오. std :: multiset 및 캐시 라인 쓰레기에서 메모리 alloc/free를 갖는 것이 좋습니다. Cache 라인 쓰레기는 나중에 죽입니다. STL 할당 규칙을 위반하지 않고 정적 상태를 제공하는 약간의 작업이 있습니다.

정확히 2의 특수 알고만큼 좋지는 않지만 고정 된 k<<n, (2N+델타*N) 델타가 작은 곳을 추측 할 것입니다. 내 DEK ACP Vol3 S & S가 포장되어 있고 델타의 추정치가 조금 더 많은 작업이라고 생각합니다.

평균 최악은 반대 순서가 있고 모든 별개 일 때 n (log (k-1) + 2)를 추측 할 것입니다.

가장 좋은 것은 2n + k (log k)입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top