정렬 된 배열의 모드는 어떻게 찾습니까?

Question

배열의 모드를 찾기위한 함수를 작성해야합니다. 그러나 나는 알고리즘을 생각해 내는데 익숙하지 않다. 나는 다른 사람이 이것을 어떻게하는지 알기를 바라고있다.

나는 배열의 크기와 각 요소의 값을 알고 있으며 배열을 최소에서 최대로 정렬했습니다.

배열

모드와 같은 모드 함수로 전달 될 = findMode (arrayPointer, sizePointer);

UPDATE : 사람이 저를 정렬 할 수 있습니다 경우 비록 내가이 알고리즘을 잡고이

int findMode(int *arrPTR, const int *sizePTR) 
{ 
    int most_found_element = arrPTR[0]; 
    int most_found_element_count = 0; 
    int current_element = arrPTR[0]; 
    int current_element_count = 0; 
    int count; 
    for (count = 0; count < *sizePTR; count++) 
    { 
     if(count == arrPTR[count]) 
      current_element_count++; 
     else if(current_element_count > most_found_element) 
     { 
      most_found_element = current_element; 
      most_found_element_count = current_element_count; 
     } 
     current_element = count; 
     current_element_count=1; 
    } 

    return most_found_element; 
} 

여전히 문제가 발생합니다 시도했습니다

코멘트를 읽은 후. 저는 벡터를 사용한 적이 없으므로 다른 예제를 이해하지 못합니다.

Answer 1

set most_found_element to the first element in the array 
set most_found_element_count to zero 
set current_element to the first element of the array 
set current_element_count to zero 
for each element e in the array 
    if e is the same as the current_element 
     increase current_element_count by one 
    else 
     if current_element_count is greater than most_found_element_count 
      set most_found_element to the current_element 
      set most_found_element_count to current_element_count 
     set current_element to e 
     set current_element_count to one 
if current_element_count is greater than most_found_element_count 
    set most_found_element to the current_element 
    set most_found_element_count to current_element_count 
print most_found_element and most_found_element_count 

나는 이름이 그것을 설명 할 생각도하지만, 여기에 우리가 간다 :

When we start, no element has been found the most times 
    so the "high-score" count is zero. 
Also, the "current" value is the first, but we haven't looked at it yet 
    so we've seen it zero times so far 
Then we go through each element one by one 
    if it's the same as "current" value, 
    then add this to the number of times we've seen the current value. 
    if we've reached the next value, we've counted all of the "current" value. 
    if there was more of the current value than the "high-score" 
     then the "high-score" is now the current value 
    and since we reached a new value 
     the new current value is the value we just reached 
Now that we've seen all of the elements, we have to check the last one 
    if there was more of the current value than the "high-score" 
    then the "high-score" is now the current value 
Now the "high-score" holds the one that was in the array the most times! 

이 또한주의 : 내 원래 알고리즘/코드는 버그를 가지고, 우리가 루프가 끝난 후에 "현재"의 추가 점검을 수행합니다. "마지막 이후의 것"을 찾지 않습니다.

Answer 2

거의 모든 것이 있습니다.

배열이 정렬된다는 이점을 활용할 수 있습니다.

는 그냥 현재 동일한 연속 숫자를 모두 배열 유지 트랙을 통해 이동하고 동일한 연속 번호의 큰 숫자는 그 시점까지 발견 (그리고 어떤 수를 생산)했다. 결국 당신은 동등한 연속 번호의 가장 큰 수와 그것을 생성 한 번호를 갖게됩니다. 그것은 모드가 될 것입니다.

참고 하지 정렬되도록 배열을 요구 않는 솔루션는 related questionone based in the histogram approach 예를 참조.

Answer 3

힌트 :

Q : 모드를 어떻게 정의합니까?

A : 배열 내에서 카운트가 가장 큰 숫자입니다.

Q : 정렬 된 배열에서 숫자를 어떻게 계산합니까?

A : 배열을 반복하며 다음 항목이 이전 값과 같으면 해당 값의 수를 증가시킵니다.

Q : 이전 값의 수가 현재 값의 수보다 작 으면 이전 값을 모드?

A는 : 없음

Answer 4

입력 배열을 정렬하는 경우 다른 답변에서 설명한 것과 같은 방식이지만 다른 방식으로 구현하면 더 이해하기 쉽습니다.

1. 입력 배열에 대해 루프를 실행하십시오.
2. 글로벌 모드 값 및 모드 수를 유지하십시오.
3. 동일한 요소를 찾을 때까지 슬라이딩 창을 실행하십시오.
4. 로컬 동일 요소 수가 글로벌 모드 수보다 큰 경우 글로벌 모드와 모드 수를 업데이트하십시오.

C++에 작동 및 테스트 코드가 있습니다.

int mode(vector<int> a, int N) 
{ 
    int mode = a[0]; 
    int mode_count = 1; 
    int i = 0; 
    while (i < N - 1) { 
     int cur = a[i]; 
     int cur_count = 1; 
     while (a[i] == a[i + 1]) { 
      i++; 
      cur_count++; 
     } 
     if (cur_count > mode_count) { 
      mode_count = cur_count; 
      mode = a[i]; 
     } 
     i++; 
    } 
    return mode; 
}