c - 索引的微小变化需要两倍的内存和时间

Question

我针对一个问题提交了两个略有不同的解决方案，其中您删除了数组的重复元素，因此相对顺序不会改变。

在第 一种方法中，我按顺序获取输入，并按顺序存储在一个数组中，然后是两个嵌套循环，以检查输入数组中的每个元素，如果它是唯一的，我将其存储在另一个数组中。

在第二种方法中，我按顺序输入，然后以相反的顺序存储。休息是相同的，除了所需的索引/迭代器更改。

第二个花费的时间和内存是第一个的两倍。虽然，差别很小，但为什么时间会有很大的差别呢？

或者我如何才能准确检查为什么会有这种差异？

---

实际问题：给定一个由 n 个整数组成的数组 a。您的任务是通过从其中删除重复项来使这些数组独一无二。

您必须只为数组的每个元素保留最右边的匹配项并删除所有其他匹配项。不应更改剩余唯一元素的相对顺序。

第一种方法（15 毫秒，4 KB）：

#include <stdio.h>

int main(void)
{
    int n, i, c;
    scanf("%i", &n);
    int arr[n], nondupe[n];
    
    for (i = 0; i < n; i++)
        scanf("%i", arr + i);   // Store sequentially
    
    int k = n - 1;
    nondupe[k--] = arr[n - 1]; // add last element in non-duplicate array (because rightmost entries are required)
    for (i = n - 1; i > 0; i--)
        for (c = n - 1; c > k; c--) // Nested loops to iterate over all elements in both arrays
            {
                if (arr[i - 1] == nondupe[c])
                    break;
                if (c == k + 1)
                    nondupe[k--] = arr[i - 1];
            }
    printf("%i\n", n - k - 1);
    for (i = k + 1; i < n; i++)
        printf("%i ", nondupe[i]);
}

第二（30 毫秒，8 KB）：

#include <stdio.h>

int main(void)
{
    int n, i, c;
    scanf("%i", &n);
    int arr[n], nondupe[n];
    
    for (i = n; i > 0; i--)
        scanf("%i", arr + i - 1);
    
    int k = 0;
    nondupe[k++] = arr[0];
    for (i = 0; i < n; i++)
        for (c = 0; c < k; c++)
            {
                if (arr[i] == nondupe[c])
                    break;
                if (c == k - 1)
                    nondupe[k++] = arr[i];
            }
    printf("%i\n", k);
    for (i = k; i > 0; i--)
        printf("%i ", nondupe[i - 1]);
}

标签： cperformance