배열에서 3 개 이상의 동일한 객체를 찾았습니까?

Question

문제가 발생하여 누군가 해결할 수있는 방법을 알려 줄 수 있습니까? 없음 (예를 객체 내에서

{ {1,2}, {2}, {1,2}, {3,4,5}, {1,2} } 

요소 번만 표시 :

그래서, 내가 객체의 배열이 있다고 가정 할 수 있습니다 (우리는 그들이 목록에서 목록을한다고 가정 할 수 있습니다) 그래서 그런 일이 {2,2,4})과 같은 중복 객체 목록에서 두 개의 동일한 객체 만 필요하다고 생각하기 전에 문제를 멋지게 처리했지만 이제는 배열이 더 필요하고 무차별 대입이 필요했습니다. 그래서 색인을 어떻게 찾을 수 있을까요? 의 3 중 쿼드 루프 루핑으로 추악한 방법을 만들지 않고도

Th ank you

Answer 1

쉬운 방법은 키가 개체이고 값이 카운트의 정수인 경우를 사용하는 것입니다. 이렇게하면 더 빨리 찾을 수 있습니다. 충돌이없는 hashmap에 대해서는 O (nlogn) 또는 O (kn)입니다.

의사 코드 (정확한 메소드 서명을 기억하지만 당신은 아이디어를 얻을 수 없습니다) :

for (object o : myObjs) 
{ 
    int num = 0; 
    if (map.containsKey(o)) { 
     map.put(o, map.get(o) + 1); 
     num = map.get(o); 
    } else { 
     map.put(o, 1); 
     num = 1; 
    } 
    if (num == 3) 
     System.out.println("Object " + o + " has 3 members in set"); 
} 

Answer 2

당신은 당신이 좋아하는 거의 모든 비교기 구현을 사용하여 배열을 정렬 할 수 있습니다, 그것은 논리적으로 동일한 개체를 동일한 것으로보고 제공 . (글쎄, 그것은 또한보다 크고 작음의 전이 속성을 존중해야합니다.) 그런 다음 정렬 된 배열을 통해 선형 스캔을 사용하여 3 개 이상의 실행을 찾는 것이 쉽습니다.

Answer 3

Jesus Ramos의 답변을 바탕으로 기본 아이디어는 각 하위 목록을 반복하여 포함 된 요소를 몇 번이나 추적하는지 추적하는 것입니다.

#include <vector> 
using std::vector; 
#include <map> 
using std::map; 

// input data 
typedef vector<int> List; 
typedef vector< int, List > ListOfLists; 
ListOfLists input; 

// temporary map for keeping track of how many times we see 
// individual elements. if you have boost or TR1, you can 
// use unordered_map for a (possibly substantial) speedup. 
typedef map< int, int > OccuranceMap; 
OccurranceMap seen; 

// now loop through all the sub-lists 
for (ListOfLists::const_iterator outer = input.begin(), 
            oend = input.end(); 
     outer != oend; ++outer) 
{ 
    // and then iterate through all elements in each sublist 
    for (List::const_iterator inner = (*outer).begin(), 
           iend = (*outer).end(); 
      inner != iend; ++inner) 
    { 
     // and keep track of how many we've seen. using 
     // operator[] is very slightly inefficient, but 
     // shouldn't matter unless you have zillions of 
     // distinct values. 
     ++seen[*inner]; 
    } 
} 

// finally, go through the list of occurances and find those 
// that showed up 3 times (or more than 3, depends on your 
// application of course; just change the conditional). 
for (OccuranceMap::const_iterator ci = seen.begin(), 
            cend = seen.end(); 
     ci != cend; ++ci) 
    if ((*ci).second == 3) 
     cout << "saw '" << (*ci).first << "'" 
      << " " << (*ci).second << " times" << endl; 

개별 하위 목록의 길이에 따라 중복을 찾기 위해 이중 반복하는 것보다 더 나은 선택 일 수 있습니다. 발생 횟수에 대한 추가 메모리 저장 공간이 절충됩니다.