主页 / 问题 / 734567
Accepted
takecaretakecaretakecare
Asked:2020-10-23 16:58:46 +0000 UTC2020-10-23 16:58:46 +0000 UTC

两个数组的两个元素之间的最小差

  • 772

有两个数组。有必要获得第一个和第二个数组的元素之间的最小差异。例如 [1, 4, 8, 12] 和 [5, 6, 13, 19]。答案应该是1，4和5的区别。我知道你需要合并数组，取数组中两个元素之间的最小差异，但是如何合并才能让你明白这个数字来自哪个数组呢？

javascript

4 个回答

  1. 我给你这个代码。它可能没有生产力。算法：搜索“直截了当”。当然，可以注意您在问题中指出了排序数组这一事实，并且由于在方法内部的第一个嵌套循环中break;（带有附加条件）而简化了算法，但我很懒:) 我给出的程序（请注意：在 Java 中！）显示了在两个数组的哪些元素之间找到了最小的差异（模），并显示了差异本身。 for()jfind()

    Actors:
    print(int[] a, int i)-- 很好地打印数组，勾选第i-th 个元素
    delta(int a, int b)= |ab|
    find(int[] a1, int[] a2)-- 主要演员，实际执行最小差异的搜索，为我们显示整齐的数组，并指出形成最小差异的元素；此方法还显示增量本身。

    package test;

public class Main {
    static void print(int[] a, int index) {
        for (int i = 0; i < a.length - 1; i++)
            System.out.print(a[i] + ", ");
        System.out.println(a[a.length - 1]);
        for (int i = 0; i < a.length; i++) {
            int k = 1, t = a[i];
            if (t>=0) {} else {t=-t; k++;}
            while ((t = t / 10) > 0)
                k++;
            StringBuilder sb = new StringBuilder("");
            while (k-- > 0)
                sb.append(" ");
            String s = sb.toString();
            System.out.print(i == index ? "^" + s + " " : s + "  ");

        }
        System.out.println();
    }

    static int delta(int x1, int x2) {
        return Math.abs(x1 - x2);
    }

    static void find(int[] a1, int[] a2) {
        int[] min = new int[3];
        min[0] = delta(a1[0], a2[a2.length - 1]) > delta(a1[a1.length - 1], a2[0]) ? delta(a1[0], a2[a2.length - 1])
                : delta(a1[a1.length - 1], a2[0]);
        for (int i = 0; i < a1.length; i++)
            for (int j = 0; j < a2.length; j++)
                if (delta(a1[i], a2[j]) <= min[0]) {
                    min[0] = delta(a1[i], a2[j]);
                    min[1] = i;
                    min[2] = j;
                }
        print(a1,min[1]);
        print(a2,min[2]);
        System.out.println("\n");
        System.out.println("Result delta = "+min[0]);
    }

    public static void main(String[] args) {
        int[] a1 = { 1, 4, 8, 12, 18, 328, 99482}, a2 = {35, -27, 325, 9482};
        find(a1, a2);
    }
}

    out:
1, 4, 8, 12, 18, 328, 99482
                 ^           
35, -27, 325, 9482
         ^          


Result delta = 3
    • 0
  2. Best Answer

    由于您需要获得每个数组元素之间的最小差异，您可以这样做：

    1. 创建一个新的元素数组，其中一个数组的每个元素与第二个数组的每个元素的差异
    2. 按升序对结果数组进行排序
    3. 从排序数组中取零元素

    Array.prototype.allDiff = function(a){
    return this.reduce((p,c) => {
      a.forEach(e => {
        p.push(Math.abs(e-c));
      });
      return p;
    }, []);
};

console.log([1, 4, 8, 21].allDiff([5, 6, 13, 19]).sort((a,b) => a-b)[0]);

    UPD： 当然，前面的代码在性能方面根本不是最优的。稍微改善一下情况，如果不需要保存所有的差值，可以去掉输出数组的形成，立即计算最小值

    Array.prototype.allDiff = function(a){
    return this.reduce((p,c) => {
      a.forEach(e => {
        if(p === undefined){
          p = Math.abs(e-c);
        }else{
          p = Math.min(p, Math.abs(e-c));
        }
      });
      return p;
    }, undefined);
};

console.log([1, 4, 8, 21].allDiff([5, 6, 13, 19]));

    • 0 
  3.     function compare(arr1, arr2) {
let min = Math.abs(arr1[0] - arr2[0]);
  let i=0; let j=0;
  while(i < arr1.length && j < arr2.length) {

    let x = arr1[i] - arr2[j];
    if (x < 0) {
        x = -x;
        i++;
   }
    else if (x > 0) {
    j++;
   }
    else {
    return 0;
   }
    if (x < min) {
    min = x;
   }
  }
  return min;
}

    我笨拙的解决方案，谢谢大家的回答

    • 0

  4. 这取决于算法应该处理多少数据和多快，如果体积不大，那么您可以使用具有二次复杂度的最简单算法 - 在双循环中将第一个数组的每个元素与每秒进行比较并保持最小值区别。

    但是，如果您需要一种快速算法，那么我建议您使用这个算法 - 首先我们按升序对两个数组进行排序，然后我们执行与归并排序相同的操作，即 我们比较数组的合并边界并保存一对元素内的最小差异，而我们不需要生成的合并数组。该算法的复杂度是 O(N*log(N)) 用于排序加上 O(N) 用于合并。

    因为 我不太懂JavaScript，最后一个算法我写了C++代码，不难理解，可以适配JavaScript，也可以在线运行算法：

    #include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
#include <cstdlib>
using namespace std;

int main() {
    vector<int> a = {1, 4, 8, 12}, b = {5, 6, 13, 19};
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    size_t pa = 0, pb = 0;
    int min_diff = numeric_limits<int>::max();
    while (pa < a.size() && pb < b.size()) {
        min_diff = min(min_diff, abs(a[pa] - b[pb]));
        if (a[pa] < b[pb]) ++pa; else ++pb;
    }
    cout << min_diff << endl;
    return 0;
}

    在这里我学习了一点 JavaScript，并为第一个具有二次复杂度的算法编写了另一个解决方案，您可以在线运行它：

    function MinDiff(a, b) {
  var min_diff = Math.abs(a[0] - b[0]);
  for (var i = 0; i < a.length; ++i) {
    for (var j = 0; j < b.length; ++j) {
      min_diff = Math.min(min_diff, Math.abs(a[i] - b[j]));
    }
  }
  return min_diff;
}

console.log(MinDiff([1, 4, 8, 21], [5, 6, 13, 19]))

    这是另一个用 JavaScript 快速重写的 C++ 算法，在线运行：

    function MinDiff2(a, b) {
  a.sort((a,b)=>a-b);
  b.sort((a,b)=>a-b);
  var min_diff = Math.abs(a[0] - b[0]);
  var pa = 0, pb = 0;
  while (pa < a.length && pb < b.length) {
    min_diff = Math.min(min_diff, Math.abs(a[pa] - b[pb]));
    if (a[pa] < b[pb]) ++pa; else ++pb;
  }
  return min_diff;
}

console.log(MinDiff2([1, 4, 8, 21], [5, 6, 13, 19]))
    • 0

相关问题