时间戳

首页 > 解决方案 > 如何有效地比较二维数组

arrays - 如何有效地比较二维数组

问题描述

这是一个二维数组

{ {0.3072, 1.1262, 1.5706},
  {0.5068, 1.0630, 0.9470},
  {0.2470, 0.6872, 1.9626},
  {1.0686, 1.1348, 1.7506},
  {1.2874, 1.5664, 0.2470},
  {0.9072, 0.6268, 0.6684},
  {1.3164, 0.6506, 1.8462},
  {0.9072, 0.6268, 0.8706},
  {0.3072, 1.1262, 1.5706} }

我需要根据以下条件比较每一行：

  1. a 点的所有坐标都小于或等于它们对应的 b 点坐标。
  2. 至少存在一个点 a 的坐标严格小于其对应的点 b 的坐标。

如果条件为真，那么我将删除点b。这里有些例子：

  1. 第 1 点和第 4 点比较后，第 4 点将被删除。因为点 1 的所有坐标都小于它们对应的点 4 的坐标。
  2. 第 6 点和第 8 点比较后，第 8 点将被删除。因为点 6 的坐标 3 小于点 8 的对应坐标，尽管它们的其他两个坐标具有相同的值。
  3. 点 1 和点 2 比较后，不会删除任何点。因为点 1 的坐标 1 小于点 2 的对应坐标，但是点 1 的坐标 2 和坐标 3 大于点 2 的对应坐标，反之亦然。
  4. 第 1 点和第 9 点比较后，不会删除任何点。因为它们的所有坐标都是等价的。

从上面的二维数组中，我将删除点 4,7,8。

我的尝试：我正在使用嵌套循环来比较所有点

for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            int sum = 0;
            for(int k = 0; k < 3; k++){
                if(point[i][k] <= point[j][k])
                    sum++;
            }
            if(sum == 3)
                ... // delete point[j]
        }
    }

这种尝试有效，但效率不高，它的大 O 表示法是 O(n^3)。是否有任何有效的算法可以进行这种比较？

标签： arrayscalgorithmcomparison

解决方案

推荐阅读