有人可以帮我解决算法中的错误吗

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 7 年前。

Improve this question

问题链接:https://www.codechef.com/problems/PERMUT2

问题:所有测试用例都变得明确。程序执行绝对没有问题，没有错误。

您能否指出我的代码/算法中的错误:

#include <stdio.h>
#include <stdlib.h>
int index_func(int number, int *array, int x);
int main(){
    int n;
    scanf("%d", &n);
    int *nums = (int*)malloc(n*sizeof(int));
    int i;
    for(i=0; i<n; i++){
        scanf("%d", &nums[i]);
    }
    int j;
    int counter = 0;
    for(j=0; j<n; j++){

        if(nums[j] != index_func(j+1, nums, n)){
            counter = 1;
            break;

        }
    }
    if(counter == 0){
        printf("ambiguous\n");
    }else{
        printf("non ambiguous\n");
    }
    return 0;
}
int index_func(int number, int *array, int x){
    int z, index;
    for(z=0; z<x; z++){
        if(number == array[z]){
            index = z;
            return z;
        }
    }

}

Answer 1

数组中的数字以 1 开头，但 C 数组中的索引以 0 开头。对程序的快速修复是在将返回的索引与当前数字进行比较时将其添加 1:

if (nums[j] != index_func(j + 1, nums, n) + 1) ...

另一种解决方案是在扫描数组数据后将其减一来调整数组数据，以便数组包含从零开始的数字。

较大的数组可能会出现问题，因为每次调用 index_func 都会从头开始扫描整个数组，平均会遍历其中的一半。解决方案是正确的，但速度很慢。

但是您不必确定索引来进行比较。检查当前数字索引处的数字是否是当前索引就足够了。这导致了这个功能:

int is_ambiguous(const int *array, int n)
{
    int i;

    for (i = 0; i < n; i++) {
        if (array[array[i] - 1] != i + 1) return 0;
    }

    return 1;
}

关于原始代码的一些注释:

• 当数组中没有数字时，您应该从 index_funct 返回一个无效索引，可能为 -1。我知道，这种情况不应该发生在这里，但下次您复制并粘贴代码时，缺少的返回值可能会让您感到困扰。
• 您实际上并不需要 index_funct 中的变量 index。将代码片段分成小函数可以使程序控制更容易。将上述函数 is_ambiguous 与带有计数器变量和 break 的内联解决方案进行比较。
• 分配时，您还必须释放，但您没有释放。