c - 两个数组中两个元素的最小和，使得索引不相同

Question

给定两个数组ar1and ar2，我们如何从两个数组中找到两个元素的和，使得索引不相同并且它们的和最小？

但是，我写了以下内容，但我不确定是否将总和存储在临时变量中并将总和与下一次传递中的总和进行比较：

int twinArrays(int ar1_size, int* ar1, int ar2_size, int* ar2)
{
    int temp;
    for(int i = 0; i < ar1_size;i++) 
    {
        for(int j=0; j < ar2_size; j++) {
            int sum=0;
            if( i != j) 
                sum = ar1[i] + ar2[j];
            }
        }      
        return temp;
    }
}

C中的建议会有所帮助。

Answer 1

到目前为止，您的代码还不是一种解决方案，但是：

• temp应该已经初始化为足够大的值以低于想要的结果，
• 时i != j，你应该有比较sum存储temp结果如果sum低于temp，
• return被错过了。

因此，您更正的代码可能如下所示：

#include <limits.h>

int twinArrays(int ar1_size, int* ar1, int ar2_size, int* ar2)
{
    int sum_min = INT_MAX;

    /* for each element in ar1 */
    for (int i = 0; i < ar1_size; i++)
    {

        /* for each element in ar2 */
        for (int j = 0; j < ar2_size; t++)
        {
            /* go to next j if indices are the same */
            if (i != j)
            {
                /* compute sum */
                int sum = ar1[i] + ar2[j];

                /* compare to best */
                if (sum < sum_min)
                {
                    /* remember the best */
                    sum_min = sum;
                }
            }
        }        
    }

    return sum_min;   
}

Answer 2

来自 2 个数组的 2 个元素的最小和是其最小元素的总和。

但是，当任何数组的大小为 0 时会发生什么......？在这方面，问题的表述是不确定的。

以下最坏情况时间复杂度为 O(N)，最坏情况空间复杂度为 O(1)：

#include <limits.h>

int twinArrays(int ar1_size, int* ar1, int ar2_size, int* ar2)
{
    int min1 = INT_MAX, min2 = INT_MAX;

    for(int i = 0; i < ar1_size; i++)
        min1 = ar1[i] < min1? ar[1]: min1;

    for(int i = 0; i < ar2_size; i++)
        min2 = ar2[i] < min2? ar2[1]: min2;

    if (min1 > 0 && min2 > INT_MAX - min1) {
        /* handle overflow */
        return INT_MAX;
    } else if (min1 < 0 && min2 < INT_MIN - min1) {
        /* handle underflow */
        return INT_MIN;
    }
    return min1 + min2;
}