陣列中的最大值及其頻率

Question

如何編寫一個函數來查找數組中的最大值以及值出現在數組中的次數？我們不得不使用遞歸來解決這個問題。

到目前爲止，我在想它應該是這樣的：

int findMax(int[] a, int head, int last) 
{ 
    int max = 0; 

    if (head == last) { 
     return a[head]; 
    } 
    else if (a[head] < a[last]) { 
     count ++; 
     return findMax(a, head + 1, last); 
    } 
} 

我不知道這是否會雖然返回絕對值的最高值，和IM不完全知道如何改變什麼，我有

Answer 1

你並不遠。

爲了節省頻率和最大值，你可以保留一個指向結構體的指針，然後將指針傳遞給數組的開始，你想要經過的長度和指向這個結構體的指針。 請記住，您應該使用limits.h中的INT_MIN作爲您的初始最大值（請參閱下面的代碼中的reset(maxfreq *)），因爲int可以帶有負值。

下面的代碼做遞歸作業：

#include <limits.h> 

typedef struct { 
    int max; 
    int freq; 
} maxfreq; 

void reset(maxfreq *mfreq){ 
    mfreq->max = INT_MIN; 
    mfreq->freq = 0; 
} 

void findMax(int* a, int length, maxfreq *mfreq){ 

    if(length>0){ 
     if(*a == mfreq->max) 
      mfreq->freq++; 
     else if(*a > mfreq->max){ 
      mfreq->freq = 1; 
      mfreq->max = *a; 
     } 

     findMax(a+1, length - 1, mfreq); 
    } 
} 

到findMax的呼叫將本身記得多次初始長度加1，每次遞增提供指針和處理相應元件，因此這基本上只是經歷了a中的所有元素一次，沒有奇怪的分裂。

Answer 2

這正常工作與我：

#include <stdio.h> 
#include <string.h> 

// define a struct that contains the (max, freq) information 
struct arrInfo 
{ 
    int max; 
    int count; 
}; 

struct arrInfo maxArr(int * arr, int max, int size, int count) 
{ 

    int maxF; 
    struct arrInfo myArr; 

    if(size == 0) // to return from recursion we check the size left 
    { 
     myArr.max = max; // prepare the struct to output 
     myArr.count = count; 
     return(myArr); 
    } 

    if(*arr > max) // new maximum found 
    { 
     maxF = *arr; // update the max 
     count = 1; // initialize the frequency 
    } 
    else if (*arr == max) // same max encountered another time 
    { 
     maxF = max;  // keep track of same max 
     count ++;  // increase frequency 
    } 
    else    // nothing changes 
     maxF = max; // keep track of max 


    arr++;  // move the pointer to next element 
    size --; // decrease size by 1 

    return(maxArr(arr, maxF, size, count)); // recursion 

} 

int main() 
{ 
    struct arrInfo info; // return of the recursive function 

    // define an array 
    int arr[] = {8, 4, 8, 3, 7}; 

    info = maxArr(arr, 0, 5, 1); // call with max=0 size=5 freq=1 


    printf("max = %d count = %d\n", info.max, info.count); 
    return 0; 
} 

運行時，它輸出：

max = 8 count = 3 

注意
在我的代碼示例中，我假定的數字爲正（初始化max到0），我不知道你的要求，但你可以詳細說明。

Answer 3

將初始值max設置爲INT_MIN解決了許多問題。 @Rerito

但是，OP使用迭代遍歷數組的每個成員並引發每個元素的遞歸調用。因此，如果數組有1000 int，則會有大約1000個嵌套調用。

甲分而治之方法：

如果數組長度爲0或1，處理它。否則從第一和第二半找到最大的答案。酌情合併結果。除以2，1000元素數組的堆棧深度使用不會超過10個嵌套調用。

注意：無論採用哪種方式，呼叫次數都相同。不同之處在於嵌套的最大程度。在簡單的for()循環就足夠的情況下使用遞歸是有問題的。爲了征服一個更復雜的評估是遞歸的力量，因此這種方法。

---

要找到最大和使用O（LOG 2（長度））堆棧深度使用它的頻率：

#include <stddef.h> 

typedef struct { 
    int value; 
    size_t frequency; // `size_t` better to use that `int` for large arrays. 
} value_freq; 

value_freq findMax(const int *a, size_t length) { 
    value_freq vf; 

    if (length <= 1) { 
    if (length == 0) { 
     vf.value = INT_MIN; // Degenerate value if the array was size 0. 
     vf.frequency = 0; 
    } else { 
     vf.value = *a; 
     vf.frequency = 1; 
    } 
    } else { 
    size_t length1sthalf = length/2; 
    vf = findMax(a, length1sthalf); 
    value_freq vf1 = findMax(&a[length1sthalf], length - length1sthalf); 
    if (vf1.value > vf.value) 
     return vf1; 
    if (vf.value == vf1.value) 
     vf.frequency += vf1.frequency; 
    } 
    return vf; 
} 

Answer 4

提交作業的reqirements至少是值得懷疑的。僅供參考，這裏是如何應該這樣做在實際的代碼（解決您的分配，是指其他的答案）：

int findMax(int length, int* array, int* maxCount) { 
    int trash; 
    if(!maxCount) maxCount = &trash; //make sure we ignore it when a NULL pointer is passed in 

    *maxCount = 0; 
    int result = INT_MIN; 
    for(int i = 0; i < length; i++) { 
     if(array[i] > result) { 
      *maxCount = 1; 
      result = array[i]; 
     } else if(array[i] == result) { 
      (*maxCount)++; 
     } 
    } 
    return result; 
} 

永遠要做的事直線前進，你可以。