时间戳

首页 > 解决方案 > 在c中递归查找数组的第三大元素

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

问题描述

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

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

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

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

标签： calgorithmrecursion

解决方案

我的third_max(). （它使用 anassert来捕获一个短于三个元素的起始数组。）首先它对数组中的前三个元素进行就地排序；如果数组只有三个元素长，则返回第一个。如果数组的元素多于三个，则比较第一个和第四个元素，将较大的元素保留为第四个元素。最后，它调用它自递归地丢弃第一个数组元素并减少数组大小：

#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()通过创建一个唯一的正整数数组来测试该函数。它将递归函数的结果与已排序的匹配控制数组的结果进行比较，并提取倒数第​​三个元素进行比较。

Mythird_max()不调用除自身以外的任何其他函数（即没有辅助函数。）它对传入的数组具有破坏性。

推荐阅读