时间戳

首页 > 解决方案 > 简单数组算法的分治法

c - 简单数组算法的分治法

问题描述

我正在尝试采用分而治之的方法，指出列表中不遵循 n+1 序列的第一个数字。如果它们都遵循顺序，则返回-1。

例如，如果我有一个大小为 8 的数字数组：

int size = 9;
int listofNumbers[9] = { 4, 5, 6, 7, 8, 9, 3, 6, 7 };

我需要一个扫描数组并返回的函数3，因为它是第一个不符合 n+1 序列的函数。

我提出了一种使用迭代的方法，它有效：

int findFirst_iterative(int list[], int listSize)
{
    if (listSize < 1)
    {
        return -1; // empty list.
    }

    int nextNumber = list[0]; // we start with the first number in the list.

    for (int i = 1; i < listSize; i++)
    {
        if (list[i] != (nextNumber + 1))
        {
            return list[i];
        }

        nextNumber = list[i];
    }

    return -1;
}

我现在正在尝试做同样的事情，但使用的是分而治之的方法。

int findFirst_divideandconquer(int list[], int listSize)
{
    if (listSize < 1)
    {
        return -1; // the list is empty.
    }
    else if (listSize == 2)
    {
        if (list[1] != list[0] + 1)
        {
            return list[1];
        }
        else
        {
            return -1;
        }
    }

    int mid = listSize / 2;
    int listhalfA[mid];
    int listhalfB[mid];

    int overallindex = 0;
    for (int i = 0; i < mid; i++)
    {
        listhalfA[i] = list[overallindex];
        overallindex = overallindex + 1;
    }

    for (int i = 0; i < mid; i++)
    {
        listhalfB[i] = list[overallindex];
        overallindex = overallindex + 1;
    }

    int resultA = findFirst_divideandconquer(listhalfA, mid);
    if (resultA == -1)
    {
        int resultB = findFirst_divideandconquer(listhalfB, mid);
        if (resultB == -1)
        {
            return -1;
        }
        return resultB;
    }
    return resultA;
}

我遇到了一个障碍，虽然我成功地将列表分成两半，但它会返回第二个不符合顺序的数字，而不是第一个。所以上面的代码返回6而不是3，这是我需要的。我该如何解决这个问题？

标签： c

解决方案

首先，对于这项任务，除了学习之外，使用分而治之是没有意义的。您的迭代解决方案是最快的方法。只有当您想要任何非连续数字而不是第一个数字时，分而治之可能会更快。

您的分而治之方法存在三个问题。两个小错误和一个理论缺陷：

  1. 正如kaylum 指出的那样，int mid = listSize / 2; int listhalfA[mid]; int listhalfB[mid];可能会跳过一个元素。如果listSize是奇数，那么mid+mid < listSize是因为整数除法。要解决此问题，请使用int listhalfB[mid]; int listhalfB[listSize-mid];.
  2. 你的小事listSize < 1应该是listSize < 2. 由于上面的错误，到目前为止这不是问题。
  3. 分而治之需要结合部分问题的解决方案。在您的组合步骤中，您刚刚选择了第一个不是-1. 但这还不够。如果您将数组拆分1, 2, 3, 11, 12, 13为1, 2, 3并且11, 12, 13您将获得解决方案-1，-1因此-1即使正确的解决方案是11. 组合步骤也需要考虑边界处的数字。一种优雅的方法是将数组分成两个重叠的部分0 <= A <= mid，然后mid <= B <= listSize-1.

顺便说一句：复制数组会浪费大量代码行和执行时间。指定现有数组的开始和结束索引会更容易和更快：

#include <stdio.h>

int findFirstIntern(int list[], int start, int endExclusive) {
    int listSize = endExclusive - start;
    if (listSize < 2) {
        return -1;
    } else if (listSize == 2) {
        if (list[start+1] != list[start]+1) {
            return list[start+1];
        }
        return -1;
    }
    int mid = start + listSize/2;
    int result = findFirstIntern(list, start, mid+1);
    if (result != -1) {
        return result;
    }
    return findFirstIntern(list, mid, endExclusive);
}

int findFirst(int list[], int listSize) {
    return findFirstIntern(list, 0, listSize);
}

int main() {
    int list[] = {4, 5, 6, 7, 8, 9, 3, 6, 7};
    int first = findFirst(list, sizeof(list)/sizeof(int));
    printf("First non-consecutive number is %d\n", first);
    return 0;
}

如果您返回非连续数字的索引而不是数字本身，则此解决方案也适用于负数。

推荐阅读