时间戳

首页 > 解决方案 > 这两个递归函数可以合并为一个吗？

arrays - 这两个递归函数可以合并为一个吗？

问题描述

    int sorted_a(int arr[], int N)
    {

        if (N == 1 || N == 0)
            return 1;
        if (arr[N - 1] < arr[N - 2])
        {
            return 0;
        }

        return sorted_a(arr, N - 1);
    }

    int sorted_d(int arr[], int N)
    {

        if (N == 1 || N == 0)
            return 1;
        if (arr[N - 1] > arr[N - 2])
        {
            return 0;
        }

        return sorted_d(arr, N - 1);
    }

这是两个单独的递归函数，用于检查数组是按升序还是降序排序（它们为每种情况返回一个），我似乎无法找到一种方法只使用一个来完成这项工作（该函数必须只返回 1如果无论顺序如何（升序或降序）都已排序。有什么帮助吗？

编辑： 也许我的问题不够清楚。我只想创建一个问题，仅当数组已排序时才返回 1（无论升序/降序排序的方向如何），否则返回 0。

标签： arrayscsorting

解决方案

由于大多数解决方案一次只处理一个升序/降序，或者对我来说似乎过于复杂，因此这里有一个 [非递归] 版本，用于在单个函数中单次测试升序/降序：

int
sorted(const int *arr,int N)
{
    int sorted = 0x03;

    do {
        if (N < 2)
            break;

        int prev = arr[0];
        int cur;

        for (int idx = 1;  idx < N;  ++idx, prev = cur) {
            cur = arr[idx];

            // get difference
            int dif = cur - prev;

            // the same -- no change in state
            if (dif == 0)
                continue;

            // one of the sort directions is [now] wrong
            if (dif < 0)
                sorted &= 0x01;
            else
                sorted &= 0x02;

            // both directions are unsorted -- stop early
            if (! sorted)
                break;
        }
    } while (0);

    return sorted;
}

推荐阅读