时间戳

首页 > 解决方案 > 最小异或问题，超过时间限制，在少数情况下给出不同的答案

c++ - 最小异或问题，超过时间限制，在少数情况下给出不同的答案

问题描述

我正在尝试从黑客等级解决最小与异或或问题（此处），它在示例案例中运行良好，但在测试用例（T）数量为 1000 的第一个输入案例场景中，它提供了 20 个错误答案
Ex .: 10 个数字的输入数组 [853, 864, 10, 547, 954, 235, 822, 429, 628, 569] 给出的结果是 53，而正确的答案是 26。 （其余 980 是正确的），其余的都是正确的输入案例场景的时间限制超过。 我试图调试，但遇到了死胡同。
除了使用不同的排序方法（如）之外，有什么方法可以使它更可行qsort？

#include <stdio.h>
int arr[100000];
int cal[1000000];

int arrinp(int arr[], int N)
{
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }
}

void sort(int arr[], int N)
{
    int temp;
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N - 1; j++)
        {
            if (arr[i] > arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

int arrcal(int arr[], int cal[], int N)
{
    sort(arr, N);
    int ans1;
    for (int i = 0; i < N - 1; i++)
    {
        cal[i] = arr[i] ^ arr[i + 1];
    }
    sort(cal, N);
}

int main()
{
    int T, N, temp;
    scanf("%d ", &T);
    for (int i = 0; i < T; i++)
    {
        scanf("%d ", &N);
        arrinp(arr, N);
        sort(arr, N);
        arrcal(arr, cal, N);
        sort(cal, N);
        printf("%d\n", cal[0]);
    }
}

新解决方案

#include <stdio.h>
int arr[100000];
int cal[1000000];

int arrinp(int arr[], int N)
{
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }
}

int compareInt(const void *pa, const void *pb)
{
    const int *p1 = pa;
    const int *p2 = pb;
    return *p1 - *p2;
}


int arrcal(int arr[], int cal[], int N)
{
    int ans1;
    for (int i = 0; i < N - 1; i++)
    {
        cal[i] = arr[i] ^ arr[i + 1];
    }
}

int main()
{
    int T, N, temp;
    scanf("%d ", &T);
    for (int i = 0; i < T; i++)
    {
        scanf("%d ", &N);
        arrinp(arr, N);
        qsort(arr, N, sizeof(int), compareInt);
        arrcal(arr, cal, N);
        qsort(cal, N - 1, sizeof(int), compareInt);
        printf("%d\n", cal[0]);
    }
}

谢谢大家的帮助，qsort两个问题都解决了。
PS：任何人都可以解释为什么qsort在上面的例子中给出了正确的答案（10个元素）而函数sort()失败了？

标签： c++arrayscdata-structurestime-complexity

解决方案

这两个问题，错误的结果和超出的时间限制，似乎都是由这个程序引起的：

void sort(int arr[], int N)
{
    int temp;
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N - 1; j++)
        {
            if (arr[i] > arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

j, ,上的界限j < N - 1是不正确的，因为这意味着永远不会检查数组的最后一个元素。它应该是j < N。

即使是固定的，这也是 O( N 2 ) 排序。时间太长了。好的排序算法是 O( N log N )。标准 C 库中的qsort例程提供了一种有效的算法：

#include <stdlib.h>

static int CompareInt(const void *pa, const void *pb)
{
    // Convert "void *" pointers to "int *" and use them to get the int values.
    int a = * (const int *) pa, b = * (const int *) pb;
    if      (a < b)  return -1;
    else if (a == b) return  0;
    else             return +1;
}

void sort(int arr[], int N)
{
    qsort(arr, N, sizeof *arr, CompareInt);
}

此外，排序cal是不必要的。可以扫描数组的最小值而不对其进行排序。

推荐阅读