算法如何处理多个标准

Question

在数组A [n]中找到两个矩形A [i]和A [j]，使得A [i] .width > A [j] .width，并且A [i] .length - A [j] .length最长。是否有一种方法将复杂性降低为O（nlogn）？我无法想出一种在第二个矩形进行O（logn）搜索的方法。由于两个标准的可能性完全相反，排序似乎在这里没有帮助。也许我是错了吗？请指引我正确的方向。谢谢。

注：使用不同的对象并使用2个标准而不是3个的作业任务，但上下文是相同的。

- user3758745

---

按照宽度升序排列数组元素。然后向下扫描该数组，将当前长度与迄今为止遇到的最高长度相减。跟踪迄今为止遇到的最大差异（及其对应的i和j）。完成后，您将拥有最大的长度差异A[i].length-A[j].length，其中A[i].width > A[j].width。 - RBarryYoung

@RBarryYoung 您的答案是正确的，为什么不将其作为完整答案发布呢？ - Juan Lopes

@JuanLopez：感谢@RBarryYoung的建议，他提出了如何排序是第一步，而不是为与家庭作业相关的问题提供完全详细的答案。 - greybeard

Answer 1

由于这是作业，这里给出一个高层次的答案，实现留给OP自己解决:

按宽度升序排列数组元素。然后从上到下扫描该数组，将当前长度从迄今为止遇到的最大长度中减去。跟踪到目前为止遇到的最大差（以及相应的i和j）。完成后，您将得到最大长度差A[i].length-A[j].length，其中A[i].width > A[j].width

分析：对元素进行排序需要O(n*Log(n))，所有其他步骤需要O(n)。

- RBarryYoung

Answer 2

这里是一些Java代码来实现相同的功能：

  import java.util.Arrays;
  import java.util.Comparator;
  import java.util.Random;

  public class RequiredRectangle {

    public static void main(String[] args) {
        // test the method
        int n=10;
        Rectangle[] input = new Rectangle[n];
        Random r = new Random();
        for(int i=0;i<n;i++){
            input[i] = new Rectangle(r.nextInt(100)+1,r.nextInt(100)+1);
        }

        System.out.println("INPUT:: "+Arrays.deepToString(input));

        Rectangle[] output = getMaxLengthDiffAndGreaterBreadthPair(input);
        System.out.println("OUTPUT:: "+Arrays.deepToString(output));

    }

    public static Rectangle[] getMaxLengthDiffAndGreaterBreadthPair(Rectangle[] input){
        Rectangle[] output = new Rectangle[2];

        Arrays.sort(input, new Comparator<Rectangle>() {
            public int compare(Rectangle rc1,Rectangle rc2){
                return rc1.getBreadth()-rc2.getBreadth();
            }
        });

        int len=0;
        Rectangle obj1,obj2;
        for(int i=0;i<input.length;i++){
            obj2=input[i];
            for(int j=i+1;j<input.length;j++){
                obj1=input[j];
                int temp=obj1.getLength() - obj2.getLength();

                if(temp>len && obj1.getBreadth() > obj2.getBreadth()){
                    len=temp;
                    output[0]=obj1;
                    output[1]=obj2;
                }
            }
        }
        return output;
    }
  }

  class Rectangle{
    private int length;
    private int breadth;

    public int getLength(){
        return length;
    }

    public int getBreadth(){
        return breadth;
    }

    public Rectangle(int length,int breadth){
        this.length=length;
        this.breadth=breadth;
    }

    @Override
    public boolean equals(Object obj){
        Rectangle rect = (Rectangle)obj;

        if(this.length==rect.length && this.breadth==rect.breadth)
            return true;

        return false;
    }

    @Override
    public String toString(){
        return "["+length+","+breadth+"]";
    }
  }

`

样例输出：

INPUT:: [[8,19], [68,29], [92,14], [1,27], [87,24], [57,42], [45,5], [66,27], [45,28], [29,11]]
OUTPUT:: [[87,24], [8,19]]

- Deepak Singh

---

此回答缺乏算法描述和资源使用分析 - 问题的一部分是“有没有一种方法将复杂度降至O（nlogn）？” - greybeard

感谢您的回答，您在那里有2个循环。这不是O(n^2)的复杂度吗？ - user3758745