文章/答案/技术大牛

发布

社区首页 >问答首页 >找到所有可能的对的最小差

问找到所有可能的对的最小差
EN

Stack Overflow用户

提问于 2022-02-23 15:12:06

回答 1查看 136关注 0票数 -1

给定3个数字排序数组：

int[] a;
int[] b;
int[] c;

有必要找到三个差最小的数字：(a_i- b_j)^2 + (b_j - c_k)^2 + (a_i - c_k)^2 -> min

例如：

int[] a = {7, 10, 12};
int[] b = {3, 4, 6, 9};
int[] c = {1, 2, 5, 8};

结果应该是7 6 8(或7 6 5)，因为(7 - 6)^2 + (6 - 5)^2 + (7 - 5)^2 = 6 = min

解决这个问题的最佳方法是什么？

我试过使用3个变量并根据最小项来增加它们，但没有成功。下面是用C++编写的算法：

void printThreeClosest(int[] a, int[] b, int[] c) {
    int64_t diff = (a[0] - b[0]) * (a[0] - b[0]) +
                   (b[0] - c[0]) * (b[0] - c[0]) +
                   (a[0] - c[0]) * (a[0] - c[0]);

    int i_res = 0, j_res = 0, k_res = 0, i = 0, j = 0, k = 0;

    while (i < a.size() && j < b.size() && k < c.size()) {
        int first_term = (a[i] - b[j]) * (a[i] - b[j]);
        int second_term = (b[j] - c[k]) * (b[j] - c[k]);
        int third_term = (a[i] - c[k]) * (a[i] - c[k]);

        int min_term = std::min(a[i], std::min(b[j], c[k]));

        int64_t current_diff = first_term + second_term + third_term;

        if (current_diff < diff) {
            diff = current_diff;
            i_res = i, j_res = j, k_res = k;
        }

        if (diff == 0) {
            break;
        }

        if (first_term == min_term) {
            ++k;
        } else if (second_term == min_term) {
            ++i;
        } else {
            ++j;
        }
    }

    std::cout << a[i_res] << " " << b[j_res] << " " << c[k_res] << "\n";
}

c++

arrays

回答 1

Stack Overflow用户

发布于 2022-02-23 16:17:24

海事组织，直截了当，但O(n^3)的解决方案可能是：

void printThreeClosest(int[] a, int[] b, int[] c) {
    int minVal = -1;
    int resa, int resb, int resc;

    for(int i=0; i<a.length && minVal != 0; i++) {
        int x = a[i];
        for(int j=0; j<b.length && minVal != 0; j++) {
            int y = b[j];
            for(int k=0; k<c.length && minVal != 0; k++) {
                int z = c[k];
                int sumOfSqr = ( ((x-y)*(x-y)) + ((y-z)*(y-z)) + ((z-x)*(z-x)) );
                if (minVal < 0) {
                    minVal = sumOfSqr;
                    resa=x; resb=y; resc=z;
                } else if (sumOfSqr < minVal) {
                    minVal = sumOfSqr;
                    resa=x; resb=y; resc=z;
                }
            }
        }
    };
    std::cout << resa << ' ' << resb << ' ' << resc << std::endl;
}

这个在Javascript中实现的快速测试解决方案如下：

const a = [7, 10, 12];
const b = [3, 4, 6, 9];
const c = [1, 2, 5, 8];

let minVal = -1;
let result = [];

const sumOfSquares = (x, y, z) => ( ((x-y)*(x-y)) + ((y-z)*(y-z)) + ((x-z)*(x-z)) );

for (let i=0; i < a.length && minVal !== 0; i++) {
    for (let j=0; j < b.length && minVal !== 0; j++) {
    for (let k=0; k < c.length && minVal !== 0; k++) {
        const tempSum = sumOfSquares(a[i], b[j], c[k]);
        if (minVal < 0) {
        minVal = tempSum;
        result = [a[i], b[j], c[k]];
      } else if (tempSum < minVal) {
        minVal = tempSum;
        result = [a[i], b[j], c[k]];
      }
    }
  }
}

console.log('result: ', result);

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/71239492

复制

相似问题

问找到所有可能的对的最小差
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找到所有可能的对的最小差EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问找到所有可能的对的最小差
EN