c - 在c中递归查找数组的第三大元素

Question

这个问题是在我的计算机科学考试几个月后被问到的，但我找不到任何答案。有时我想知道它是否可能，这是原型(prototype)。

目标是返回整数数组中第三大元素的索引。我已经学会了如何找到最大和第二大元素，但这似乎很难。

int third_max(int arr[],int size); 

我正在寻找一个递归函数，它可能只能通过一个函数帮助找到它，即 max(a,b)，它返回 a,b 的最大值。编辑:没有重复的元素

Answer 1

我的third_max()实现。 (它使用 assert 来捕获少于三个元素的起始数组。)首先，它对数组中的前三个元素进行排序；然后再对数组中的前三个元素进行排序。如果数组只有三个元素长，则返回第一个。如果数组超过三个元素，它将比较第一个和第四个元素，保留较大的作为第四个元素。最后，它调用它的 self 递归地删除第一个数组元素并减少数组大小:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define ARRAY_SIZE (10)

int third_max(int array[], size_t size) {
    assert(size > 2);

    if (array[0] > array[1]) {
        int temp = array[1];
        array[1] = array[0];
        array[0] = temp;
    }

    if (array[1] > array[2]) {
        int temp = array[2];
        array[2] = array[1];
        array[1] = temp;
    }

    if (array[0] > array[1]) {
        int temp = array[1];
        array[1] = array[0];
        array[0] = temp;
    }

    if (size == 3) {
        return array[0];
    }

    if (array[0] > array[3]) {
        array[3] = array[0];
    }

    return third_max(array + 1, size - 1);
}

int compare(const void *a, const void *b) {
    const int *aa = a;
    const int *bb = b;
    return (*aa > *bb) - (*aa < *bb);
}

int main() {
    int array[ARRAY_SIZE], control[ARRAY_SIZE];

    srandomdev();

    for (int i = 0; i < ARRAY_SIZE; i++) {

        int x = -1;

        while (x == -1) {

            x = (random() & 127) - 63;

            for (int j = 0; j < i; j++) {
                if (array[j] == x) { // avoid duplicates
                    x = -1;
                    break;
                }
            }
        }

        control[i] = array[i] = x;
    }

    printf("[");
    for (int i = 0; i < ARRAY_SIZE; i++) {
        printf("%d, ", array[i]);
    }
    printf("] -> ");

    printf("%d ", third_max(array, ARRAY_SIZE));

    qsort(control, ARRAY_SIZE, sizeof(int), &compare);

    printf("(%d)\n", control[ARRAY_SIZE - 3]);

    return 1;
}

其余代码通过创建唯一正整数数组来测试 third_max() 函数。它将递归函数的结果与已排序的匹配控制数组的结果进行比较，并提取倒数第​​三个元素进行比较。

我的third_max()不会调用除自身之外的任何其他函数(即没有辅助函数。)它对传入的数组具有破坏性。