algorithm - 寻找非支配对的算法

Question

给定的是成对的整数(a1,b1),...,(an,bn)。如果和，对i由对“支配” 。什么是快速确定不受任何其他对支配的对列表的算法？jai < ajbi < bj

我们可以检查所有对，并且对于每一对，通过再次遍历所有对来检查它是否被任何其他对支配。这个算法是有序的n^2。是否有顺序算法n或n log n？

Answer 1

我们可以及时找到非支配对O(n log n)。

按降序对对进行排序，a_i然后对这些对进行迭代。此外，跟踪b迄今为止看到的最大值，b_max. 在每一步，如果下一个(a_i,b_i) 对的b值大于b_max，则将其附加到答案列表并更新b_max。最终的答案列表将是非支配对。

正确性：当且仅当某对具有较大的a 值和较大的 时，一对是支配的b。当我们考虑一对时，我们将其b值精确地b与具有较大a' 的对中的最大值进行比较，因此当且仅当它不被支配时，我们才将一对添加到列表中。

运行时：按值对对进行排序需要O(n log n)时间。迭代需要O(n)时间，因此整体运行时间为O(n log n).

Answer 2

如果我理解正确的话，一个非支配对是这样一个，即 a 或 b 分别大于或等于 a 和 b 的最大值。

因此，您只需要为 a 和 b 找到这样的最大值（a for 循环 O(n)），然后执行另一个循环以找到满足上述条件的任何一对。总之，O(n) 时间复杂度。

Java 中的一个小例子，返回一个 ArrayList 的“非支配”对的索引：

    ArrayList<Integer>findUndominatedPairIndexes(int[][]arrayOfPairs)
    {
        ArrayList<Integer>result=new ArrayList<Integer>();
        int maxX=Integer.MIN_VALUE;
        int maxY=Integer.MIN_VALUE;
        int i=arrayOfPairs.length;
        /**
         * get the max value
         */
        for(;--i>=0;)
        {
            int x=arrayOfPairs[i][0];
            int y=arrayOfPairs[i][1];
            if (x>maxX)
            {
                maxX=x;
            }
            if (y>maxY)
            {
                maxY=y;
            }
        }
        for(i=arrayOfPairs.length;--i>=0;)
        {
            int[] pair=arrayOfPairs[i];
            if (pair[0]>=maxX||pair[1]>=maxY)
            {
                result.add(new Integer(i));
            }

        }
        return result;
    }