从三个不同的排序数组中找到三个最接近的元素（两个解决方案之间的差异）

Question

//解决方案1

void findClosest(int A[], int B[], int C[], int p, int q, int r)
{
 
    int diff = INT_MAX;  // Initialize min diff
 
    // Initialize result
    int res_i =0, res_j = 0, res_k = 0;
 
    // Traverse arrays
    int i=0,j=0,k=0;
    while (i < p && j < q && k < r)
    {
        // Find minimum and maximum of current three elements
        int minimum = min(A[i], min(B[j], C[k]));
        int maximum = max(A[i], max(B[j], C[k]));
 
        // Update result if current diff is less than the min
        // diff so far
        if (maximum-minimum < diff)
        {
             res_i = i, res_j = j, res_k = k;
             diff = maximum - minimum;
        }
 
        // We can't get less than 0 as values are absolute
        if (diff == 0) break;
 
        // Increment index of array with smallest value
        if (A[i] == minimum) i++;
        else if (B[j] == minimum) j++;
        else k++;
    }
 
    // Print result
    cout << A[res_i] << " " << B[res_j] << " " << C[res_k];
}

//解决方案2

void findClosest(int A[], int B[], int C[], int p, int q, int r)
{

//同解1

    while (i < p && j < q && k < r)
    {
        // Find minimum and maximum of current three elements
        int minimum = min(A[i], min(B[j], C[k]));
        int maximum = max(A[i], max(B[j], C[k]));
 
        // Calculate the maximum difference for the current combination
        int curDiff = abs(maximum - minimum);
 
        // Update result if current diff is less than the min
        // diff so far
        if (curDiff < diff)
        {
            res_i = i, res_j = j, res_k = k;
            diff = curDiff;
        }
 
        // If the maximum element of A is the smallest among the three,
        // we move the A pointer forward
        if (A[i] == minimum && A[i] <= B[j] && A[i] <= C[k]) i++;
 
        // If the maximum element of B is the smallest among the three,
        // we move the B pointer forward
        else if (B[j] == minimum && B[j] <= A[i] && B[j] <= C[k]) j++;
 
        // If the maximum element of C is the smallest among the three,
        // we move the C pointer forward
        else k++;
    }
 
    // Print result
    cout << A[res_i] << " " << B[res_j] << " " << C[res_k];
}

为什么第一个解的时间复杂度是O(p + q + r)，而第二个解的时间复杂度是O(NLongN)。如果第二个解决方案没有分成两半，为什么要使用二分搜索？ 第二种解决方案不是也会增加包含最小元素的数组的索引吗？

Answer 1

由于我对“C”风格编码进行了评论，因此这里类似，但仅使用 C++。这更符合 C++ 核心准则

#include <array>
#include <vector>
#include <limits>
#include <iostream>

// using namespace std; // do not use this

// the result of a find closest operation
struct find_closest_result_t
{
    int value1;
    int value2;
    int value3;
    int distance = std::numeric_limits<int>::max(); // DO NOT USE INT_MAX (that's "C")
};

// in C++ do NOT use "C" style arrays, but use std::vector (dynamic length) or std::array (fixed length)
// pass by reference to avoid copies
// pass by const, since find should never be allowed to modify the content of the vectors
// finding the closest values is like finding the mimimum distance between values

auto find_closest(const std::vector<int>& values1, const std::vector<int>& values2, const std::vector<int>& values3)
{
    find_closest_result_t result;

    // prefer range-based for loops over iterators and or index based for loops, range based for loops cannot go out of bounds
    // nowhere in the calculation do we need the index of the values so range-based for loops it is
    // 
    // Also note this algorithm shows the complexity is O(n^3) as shown by the three nested loops
    // (I did not go looking for an efficient algorithm, because my goal is to show current C++ in action)
    
    for (const auto value1 : values1)
    {
        for (const auto value2 : values2)
        {
            for (const auto value3 : values3)
            {
                // calculate the distance between the three values (no need to use individual min/max calls)
                auto distance = std::abs(value1 - value2) + std::abs(value2 - value3) + std::abs(value3 - value1);
                if (distance < result.distance)
                {
                    // update the result with the new values
                    result = { value1, value2, value3, distance };
                }
            }
        }
    }

    return result;
}

// overload the stream operator to print the result
std::ostream& operator<<(std::ostream& os, const find_closest_result_t& result)
{
    os << result.value1 << ", " << result.value2 << ", " << result.value3 << " = " << result.distance;
    return os;
}

// main function to test find_closest
int main()
{
    std::vector<int> values1{1, 4, 10};
    std::vector<int> values2{3, 2, 9 };
    std::vector<int> values3{7, 5, 6, 11};

    auto result = find_closest(values1, values2, values3);
    std::cout << result << "\n";
    return 0;
}