행에서 가장 많이 나타나는 숫자를 찾는 알고리즘 - C++

Question

하나의 문제를 해결하는 알고리즘을 만드는 데 도움이 필요합니다. 행에 여러 번 나타나는 숫자가있는 행이 있습니다. 표시되는 숫자는 대부분이 행에 얼마나 많은 시간, 예하면 :

1-1-5-1-3-7-2-1-8-9-1-2

될 것이라고 1과 5 번 나타납니다.

알고리즘이 빨라야합니다 (내 문제입니다). 아이디어가 있으십니까?

Answer 1

당신은 해시 테이블을 유지하고 mode라고 찾고있는이

h[1] = 5 
h[5] = 1 
... 

Answer 2

처럼, 그 구조에있는 모든 요소의 수를 저장할 수 있습니다. 배열을 정렬 한 다음 가장 긴 반복 시퀀스를 찾을 수 있습니다.

Answer 3

적어도 한 번씩 각 숫자를 살펴볼 필요가 있기 때문에 선형 시간보다 더 빨리 얻을 수 없습니다.

숫자가 특정 범위에 있음을 알고있는 경우 추가 배열을 사용하여 각 숫자의 합계를 계산할 수 있습니다. 그렇지 않으면 해시 테이블이 약간 느려야합니다.

이 두 가지 모두 추가 공간이 필요하지만 결과를 얻으려면 끝에 다시 반복해야합니다.

실제로 엄청난 양의 숫자가 있고 O (n) 런타임이 절대적으로 필요한 경우가 아니면 단순히 숫자 배열을 정렬 할 수 있습니다. 그런 다음 숫자를 한 번 보면서 현재 숫자의 수와 최대 발생 수를 두 변수로 유지하면됩니다. 그래서 당신은 많은 시간을 절약하면서 많은 공간을 절약 할 수 있습니다.

Answer 4

여기에 그 (N 로그 n) O이며, 단순한 하나입니다

보편적 인 방법 "을 정렬하고 긴 순서를 검색"입니다 O(nlog n)입니다 :

Sort the vector @ O(n log n) 
Create vars: int MOST, VAL, CURRENT 
for ELEMENT in LIST: 
    CURRENT += 1 
    if CURRENT >= MOST: 
     MOST = CURRENT 
     VAL = ELEMENT 
return (VAL, MOST) 

Answer 5

몇 가지 방법이 있습니다. 가장 빠른 정렬 알고리즘은 quicksort (평균, 최악의 경우 O(n^2))입니다. 또한 heapsort를 사용할 수는 있지만 평균적인 경우에는 상당히 느리지 만 최악의 경우 점근 적 복잡도는 O(n log n)입니다.

숫자에 대한 정보가 있으면 몇 가지 트릭을 사용할 수 있습니다. 숫자가 제한된 범위에서 나온다면 알고리즘의 일부를 사용하여 정렬 수를 계산할 수 있습니다. O(n)입니다.

이것이 사실이 아니라면 선형 시간에는 할 수 있지만 다른 누구도 보편적이지 않은 정렬 알고리즘이 있습니다.

Answer 6

편집 : 사용되지 않는 비교 기능을 사용하지 않았습니다.

#Python 3.1 
lst = [1,1,5,1,3,7,2,1,8,9,1,2] 

dct = {} 
for i in lst: 
    if i in dct: 
     dct[i] += 1 
    else: 
     dct[i] = 1 

mx = max(dct.keys(), key=lambda k: dct[k]) 

print('Value {0} appears {1} times.'.format(mx, dct[mx])) 

>>> 
Value 1 appears 5 times. 

Answer 7

선형 시간 문제 (입력 항목 수에 선형)를 해결하는 알고리즘이 있습니다 : 여기

파이썬 3.1 IMPL입니다.아이디어는 해시 테이블을 사용하여 입력의 각 값에 값이 표시된 횟수를 나타내는 계수를 연결하는 것입니다. 예상 입력에 대해 프로파일을 작성하고 이것이 요구 사항을 충족시키는 지 확인해야합니다.

여기에는 O(n) 여분의 공백이 사용됩니다. 이것이 받아 들일 수 없다면 다른 사람들이 제안한 것처럼 입력을 정렬하는 것이 좋습니다. 그 해결책은 시간에 O(n log n)이고 공간에 O(1)이 될 것입니다.

여기 std::tr1::unordered_map을 사용하여 C의 구현 ++ 같습니다

#include <iostream> 
#include <unordered_map> 

using namespace std; 
using namespace std::tr1; 

typedef std::tr1::unordered_map<int, int> map; 

int main() { 
    map m; 

    int a[12] = {1, 1, 5, 1, 3, 7, 2, 1, 8, 9, 1, 2}; 
    for(int i = 0; i < 12; i++) { 
     int key = a[i]; 
     map::iterator it = m.find(key); 
     if(it == m.end()) { 
      m.insert(map::value_type(key, 1)); 
     } 
     else { 
      it->second++; 
     } 
    } 
    int count = 0; 
    int value; 
    for(map::iterator it = m.begin(); it != m.end(); it++) { 
     if(it->second > count) { 
      count = it->second; 
      value = it->first; 
     } 
    } 

    cout << "Value: " << value << endl; 
    cout << "Count: " << count << endl; 
} 

알고리즘은 각 정수가 나타나는 횟수를 카운트하는 해시 테이블에서 키로 입력 된 정수를 사용하여 작동한다. 따라서 알고리즘의 열쇠 (의도 된 말장난)이 해시 테이블을 구축하고있다 : 우리는 우리의 입력 목록에서 i 번째 요소에서 찾고있다

int key = a[i]; 
map::iterator it = m.find(key); 
if(it == m.end()) { 
    m.insert(map::value_type(key, 1)); 
} 
else { 
    it->second++; 
} 

그래서 여기에. 그러면 우리가하는 일은 우리가 이미 그것을 보았는지를 보는 것입니다. 그렇지 않은 경우이 새 정수가 포함 된 해시 테이블에 새 값을 추가하고 초기 수를 나타내는 첫 번째 카운터가 처음으로 표시된다는 것을 나타냅니다. 그렇지 않으면이 값과 관련된 카운터를 증가시킵니다.

int count = 0; 
int value; 
for(map::iterator it = m.begin(); it != m.end(); it++) { 
    if(it->second > count) { 
     count = it->second; 
     value = it->first; 
    } 
} 

는 현재 두 가지 값이 나타나는 경우를 처리 할 논리가 없다 : 우리가이 표를 구축하면

, 그것은 단순히 대부분의 표시를 찾기 위해 값을 통해 실행의 문제 동일한 횟수와 횟수는 모든 가치 중에서 가장 큽니다. 자신의 필요에 따라 스스로 처리 할 수 ​​있습니다.

Answer 8

여기서 얻을 수있는 가장 좋은 시간 복잡성은 O (n)입니다. 마지막 요소는 모드를 결정하는 요소 일 수 있기 때문에 모든 요소를 ​​살펴야합니다.

해결 방법은 시간이나 공간이 더 중요한지 여부에 달려 있습니다.

공간이 더 중요한 경우 목록을 정렬 한 다음 가장 긴 연속 요소 시퀀스를 찾을 수 있습니다.

시간이 중요한 경우 각 요소의 발생 횟수 (예 : 해싱 요소 -> 개수)를 유지하면서 목록을 반복 할 수 있습니다. 이 작업을 수행하는 동안 최대 개수의 요소를 추적하고 필요한 경우 전환합니다.

모드가 대부분 요소 인 경우 (이 값이 배열에 n/2 개 이상의 요소가있는 경우) O(n) speed and O(1) space efficiency을 얻을 수 있습니다.

Answer 9

파이썬 2.6 솔루션은 아래 각 숫자의 수를 제공

>>> from collections import defaultdict 
>>> lst = [1,1,5,1,3,7,2,1,8,9,1,2] 
>>> d = defaultdict(int) 
>>> for i in lst: 
...  d[i] += 1 
... 
>>> max_occurring = max((v, k) for k, v in d.items()) 
>>> print "%d occurs %d times" % (max_occurring[1], max_occurring[0]) 
1 occurs 5 times 

Answer 10

. 시간과 공간면에서 맵을 사용하는 것보다 나은 접근 방법입니다. 가장 많은 횟수로 나타난 번호를 가져와야하는 경우 이전 번호보다 좋지 않습니다.

편집 :이 방법은 부호없는 숫자와 1부터 시작하는 숫자에 유용합니다.

std::string row = "1,1,5,1,3,7,2,1,8,9,1,2"; 
    const unsigned size = row.size(); 
    int* arr = new int[size]; 
    memset(arr, 0, size*sizeof(int)); 
    for (int i = 0; i < size; i++) 
    { 
     if (row[i] != ',') 
     { 
      int val = row[i] - '0'; 
      arr[val - 1]++; 
     } 
    } 

    for (int i = 0; i < size; i++) 
     std::cout << i + 1 << "-->" << arr[i] << std::endl; 

Answer 11

일반 C++ 솔루션 :

#include <algorithm> 
#include <iterator> 
#include <map> 
#include <utility> 

template<class T, class U> 
struct less_second 
{ 
    bool operator()(const std::pair<T, U>& x, const std::pair<T, U>& y) 
    { 
     return x.second < y.second; 
    } 
}; 

template<class Iterator> 
std::pair<typename std::iterator_traits<Iterator>::value_type, int> 
most_frequent(Iterator begin, Iterator end) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type vt; 
    std::map<vt, int> frequency; 
    for (; begin != end; ++begin) ++frequency[*begin]; 
    return *std::max_element(frequency.begin(), frequency.end(), 
          less_second<vt, int>()); 
} 

#include <iostream> 

int main() 
{ 
    int array[] = {1, 1, 5, 1, 3, 7, 2, 1, 8, 9, 1, 2}; 
    std::pair<int, int> result = most_frequent(array, array + 12); 
    std::cout << result.first << " appears " << result.second << " times.\n"; 
} 

하스켈 솔루션 :

import qualified Data.Map as Map 
import Data.List (maximumBy) 
import Data.Function (on) 

count = foldl step Map.empty where 
    step frequency x = Map.alter next x frequency 
    next Nothing = Just 1 
    next (Just n) = Just (n+1) 

most_frequent = maximumBy (compare `on` snd) . Map.toList . count 

example = most_frequent [1, 1, 5, 1, 3, 7, 2, 1, 8, 9, 1, 2] 

짧은 하스켈 솔루션 스택 오버 플로우의 도움이 :

이 이후

import qualified Data.Map as Map 
import Data.List (maximumBy) 
import Data.Function (on) 

most_frequent = maximumBy (compare `on` snd) . Map.toList . 
       Map.fromListWith (+) . flip zip (repeat 1) 

example = most_frequent [1, 1, 5, 1, 3, 7, 2, 1, 8, 9, 1, 2] 

Answer 12

숙제 I입니다 그것이 괜찮다고 생각해. 다른 언어로 솔루션을 제공하십시오. 다음과 같은 스몰 토크 뭔가

좋은 출발점이 될 것입니다 : 내가 배열 및 여러 루프가 그 일을 시도했습니다

SequenceableCollection>>mode 
    | aBag maxCount mode | 

    aBag := Bag new 
      addAll: self; 
      yourself. 
    aBag valuesAndCountsDo: [ :val :count | 
    (maxCount isNil or: [ count > maxCount ]) 
     ifTrue: [ mode := val. 
       maxCount := count ]]. 

    ^mode