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

Question

我正在尝试从黑客级别解决 Minimum AND xor OR 问题 (here)，它在示例案例中运行良好，但在第一个输入中测试案例（T）数量为 1000 的案例场景提供了 20 错误答案
示例：输入 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 解决了这两个问题。
P.S.: 任何人都可以解释为什么 qsort 在上面的例子中给出了正确的答案（10 个元素）而函数 sort() 失败了？

Answer 1

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

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²) 排序。这需要太长时间。好的 sorting algorithms 是 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 是不必要的。无需排序即可扫描数组的最小值。

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

Minimum XOR problem, exceeds the time limit and gives different answers in few cases

c

c++

arrays

time-complexity

data-structures