9

在我将实际测试作为工作申请的一部分之前，我正在尝试 Codility 的演示问题。他们的一个演示是一个问题，涉及计算磁盘阵列的磁盘交叉点的数量。

任务描述是

给定一个包含 N 个整数的数组 A，我们在 2D 平面中绘制 N 个圆盘，使得第 I 个圆盘以 (0,I) 为中心，半径为 A[I]。如果 J ≠ K 并且第 J 和第 K 圆盘至少有一个公共点，我们说第 J 个圆盘和第 K 个圆盘相交。写一个函数：class Solution { public int number_of_disc_intersections(int[] A); } ，给定一个描述 N 个圆盘的数组 A，如上所述，返回相交圆盘对的数量。

您可以在此处查看测试。

有一些明显的 O(n^2) 时间复杂度解决方案，但目标是 O(n*log(n))。

我想出了这个，它适用于我提供的任何示例，以及 codility 给出的简单测试用例（ [1, 5, 2, 1, 4, 0] ），但 Codility 告诉我它在大多数情况下都失败了其他人，但我不太明白为什么。

它当然应该是 O(n log n)，因为将 n 个磁盘中的每一个添加到 TreeSet 是 log n，然后我们遍历每个磁盘，只有 O(1) 操作 TreeSet.headSet()。

import java.util.*;

class Circle implements Comparable<Circle> {
  long edge;
  int index;

  Circle (long e, int i){
    edge = e;
    index = i;
  }

  long getRightAssumingEdgeIsLeft(){
    return (long)(2*index - edge + 1);
  }

  @Override
  public int compareTo(Circle other){
    return Long.valueOf(edge).compareTo(other.edge);
  }
}

class Solution {
  public int number_of_disc_intersections ( int[] A ) {
    int N = A.length;
    if (N<2) return 0;
    int result = 0;

    SortedSet<Circle> leftEdges  = new TreeSet<Circle>();
    for (int i=0; i<N; i++) {
      leftEdges.add( new Circle( (long)(i-A[i]), i ) );
    }
    int counter = 0;
    for (Circle c : leftEdges) {
      long rightEdge = c.getRightAssumingEdgeIsLeft();
      Circle dummyCircle = new Circle (rightEdge, -1);
      SortedSet<Circle> head = leftEdges.headSet(dummyCircle);
      result +=  head.size() - counter;
      if (result > 10000000) return -1;
      counter++;
    }
    return result;
  }
}
4

9 回答 9

17

不同的算法（O(N log N)）：

这个糟糕的场景图：

在此处输入图像描述

可以翻译成范围列表：（不完全一样的场景）

图 2 在此处输入图像描述

O(N log N)：我们首先对标记进行排序，如果我们想将切线圆盘计算为重叠，请注意绿色标记出现在红色标记之前。

O(N)：我们从左到右扫描，total初始= 0和overlaps初始= 0。每次我们击中一个绿色标记，total += 1和每个红色标记，total -= 1。此外，在每个绿色标记处，if total > 0, then overlaps += total。

图2中的黑色数字在total每一步；橙色是overlaps。

那么overlaps应该就是答案了。

在此处查看粗略的实现：http: //ideone.com/ggiRPA

于 2012-12-26T15:37:06.367 回答
3

有一个更简单的方法...

  1. 创建 2 个包含 N 个元素的数组（leftEdge、rightEdge）。
  2. 对于每个元素计算左右边缘（索引 -/+ 值）并将其设置在数组中。
  3. 对数组进行排序。
  4. 对于 rightEdge 数组中的每个元素，循环遍历 leftEdge 数组以找到第一个更大或相等的元素。保存剩余元素的数量和当前索引。对于从保存的索引开始循环的下一个元素...

这样我们实际上只循环遍历每个排序数组一次，所以算法的复杂度是 O(N log N)。

于 2013-03-30T00:27:19.790 回答
2

此方法不需要任何特殊类，例如圆形或复杂容器，例如 PriorityQueue 或 TreeSet。只需要简单的整数数组。它是 O(N * logN)。语言是Java。

public int numberOfDiscIntersections(int [] A) {
    // 0 <= A.length <= 100,000
    // 0 <= A[i] <= 2147483647
    int [] leftEdge = new int[A.length];
    int [] rightEdge = new int[A.length];

    int maxLength = 100000;
    // maxLength is used to prevent integers > 2147483647
    // and integers < -2147483647
    for (int i = 0; i < A.length; i++) {
        leftEdge[i] = i - A[i];
        rightEdge[i] = i - maxLength + A[i];
    }
    Arrays.sort(leftEdge);
    Arrays.sort(rightEdge);

    int sum = mergeAndCountOverlaps(leftEdge,rightEdge, maxLength);
    return sum;
}

合并例程是来自合并排序的修改合并。它合并两个排序数组，保持排序顺序不变并添加重叠计数功能。在这种情况下，我们不需要返回合并后的数组，只需要返回重叠计数。

private int mergeAndCountOverlaps(int[] leftEdge, int [] rightEdge, int maxLength) {
    int leftIndex = 0;
    int rightIndex = 0;
    int sum = 0;
    int total = 0;
    while ((leftIndex < leftEdge.length) || (rightIndex < rightEdge.length)) {
        if ((leftIndex < leftEdge.length) && (rightIndex < rightEdge.length)) {
            boolean compareLeftEdgeandRightEdge;
            if (leftEdge[leftIndex] < -2147483647 + maxLength) {
                compareLeftEdgeandRightEdge = leftEdge[leftIndex] <= rightEdge[rightIndex] + maxLength;
            } else {
                compareLeftEdgeandRightEdge = leftEdge[leftIndex] - maxLength <= rightEdge[rightIndex];
            }
            if (compareLeftEdgeandRightEdge) {
                // a new left edge
                sum += total;
                if (sum > 10000000) {
                    return -1;
                }
                total++;
                leftIndex++;
            } else {
                // a new right edge
                total--;
                rightIndex++;
            }
        } else if (leftIndex < leftEdge.length) {
            // a new left edge
            sum += total;
            if (sum > 10000000) {
                return -1;
            }
            total++;
            leftIndex++;
        } else if (rightIndex < rightEdge.length) {
            // a new right edge
            total--;
            rightIndex++;
        }
    }
    return sum;
}
于 2014-07-04T05:08:54.747 回答
1

第一件事：你定义了 compareTo() 但不是 equals()。TreeSet JavaDoc 说：“集合维护的顺序（无论是否提供显式比较器）必须与 equals 一致”

其他奇怪：我不明白这个edge领域是什么，也不明白你为什么把它设置为i - A[i].

于 2012-12-26T15:26:14.400 回答
0

我做了同样的演示来准备一个编程职位。我没有及时开发解决方案，结果得到了一个糟糕的分数（十几岁的时候）。然而，对这个问题很感兴趣，我继续自己完成了它。这是我的解决方案：

 ============================================================================
 Name        : cFundementalsTest.c
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(void) {

    int N = 5;
    int A[6] = {1, 5, 2, 1, 4, 0 };

        int pos_1, pos_2;
        int total;
        for(pos_1=0;pos_1<=N;pos_1++)
        {
            for(pos_2=pos_1+1;pos_2<=N;pos_2++)
            {
                if(A[pos_1] + A[pos_2] >= abs(pos_1 - pos_2))
                { // they share a common point
                    total++;
                    printf("%d and %d\n",pos_1, pos_2);
                    if(total > 10000000)
                        return(-1);
                }
            }
        }
        printf ("\n\n the total is %d",total);
}

这是看起来正确的结果：

0 and 1
0 and 2
0 and 4
1 and 2
1 and 3
1 and 4
1 and 5
2 and 3
2 and 4
3 and 4
4 and 5

 the total is 11
于 2013-06-09T19:02:12.950 回答
0

在Codility 上，您需要使用排序来解决它，对吧？下面是通过 100% 测试的 JavaScript 解决方案。

我们在轴上使用两个范围数组x。两个数组中的值相同，但首先按from参数排序，然后按to（均升序）排序。然后我们同时扫描两个阵列并跟踪重叠以计算不同的对。

您可以在jsbin中使用此代码。

function solution(arr) {
  const r1 = arr.map((n, i) => ({from: i - n, to: n + i})).sort((a, b) => a.from - b.from)
  const r2 = r1.slice().sort((a, b) => a.to - b.to)
  let i = 0, j = 0
  let overlaps = 0
  let pairs = 0

  while (i < r1.length || j < r2.length) {
    if (i < r1.length && r1[i].from <= r2[j].to) {
      pairs += overlaps
      if (pairs > 10000000) {
        return -1
      }
      overlaps++
      i++
    } else {
      overlaps--
      j++
    }
  }
  return pairs
}
于 2019-03-28T21:05:00.847 回答
0 
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        long[] leftpoint=new long[A.length];
        long[] rigthpoint=new long[A.length];
        if(A.length<2)return 0;
    
        for(int i=0;i<A.length;++i){
            leftpoint[i]=-A[i];
            leftpoint[i]+=i;
            rigthpoint[i]=A[i];
            rigthpoint[i]+=i;
        }
        Arrays.sort(leftpoint);
        Arrays.sort(rigthpoint);
        int intersection =0;
        int j=0;
        int i=0;
        int open=0;
        while(i<A.length&&j<A.length){
             if(rigthpoint[i]>=leftpoint[j]){
                   intersection+=open; 
                   open++; 
                   j++;
             }else{
                 open--;
                 i++;
             }
             if(intersection>10000000)return -1;
            }
        return intersection;
    }
}

1）创建两个数组，一个用于圆圈的左侧，一个用于右侧 2）对数组进行排序 3）创建一个变量以保持您通过的左侧点的数量少于您通过的右侧点（打开），一个用于ans(intersection) and tow to run on the array 4）我们都有尚未关闭的开放点！对于任何小于左点的右点我们有一些额外的交点作为尚未关闭的点的数量所以我们将它们添加到答案 + (open++;"new open point 因为我们已经到达新的左点") 如果我们到达一个关闭的点，我们会从开放的圆圈中删除一个，因为一个圆圈将不再位于另一个交叉点 该算法的想法是注意每个左点与仅比它小的左点相交，因此我们只能从左数左数比我们多多少！重要的是要理解，当有一个点关闭一个圆时，其中一个圆不再参与“开--”，因此如果左点小于的未闭合圆的数量仍然减去每个较大的左点检查点

于 2021-03-05T14:58:20.117 回答
0

这是 Python 中具有 O(N*LOG(N)) 时间复杂度的简单代码。

让我们描述一下代码的逻辑。

  1. 我将 i（中心）和 A[i]（半径）转换为起点和终点。

    • 开始= iA[i]
    • 结束= i+A[i]

  2. 将点添加到元组列表（开始/结束点，“打开或关闭状态”）

  3. 根据开始/结束（升序）和“打开或关闭状态”（降序）对列表进行排序。在半径 = 0 的情况下，避免在“打开”状态之前“关闭”。

  4. 从最低点到最高点（X 轴从左到右）开始处理，如果是“开放”点，则将其添加到相交的总和中，否则，只需减少开放点的数量（total_open）。

    import operator
def solution(A):
 intersects=0
 n=len(A)
 points=[]
 for i in range(n):
     points.append((i-A[i],"open"))
     points.append((A[i]+i,"close"))

 points.sort(key=operator.itemgetter(1),reverse=True)
 points.sort(key=operator.itemgetter(0))
 total_open=0
 for i in points:
     if (i[1]=="open"):
         intersects+=total_open
         total_open+=1
     if(i[1]=="close"):
         total_open-=1
     #print("intersects", intersects,"\t Total:",total_open)
 if(intersects>10000000):
     return -1
 return intersects
于 2021-11-24T15:28:38.217 回答
-2

假设 j 总是大于 i，为了满足两个圆相互作用，下面的不等式应该总是有效的：

|R(i) - R(j)| <= j - i <= R(i) + R(j)

那是另一种说法：

abs(A[i] - A[j]) <= j - i <= A[i] + A[j]

我没有测试过，但我认为它有效。希望能帮助到你。

#include <stdlib.h>

public int number_of_disc_intersections(int[] A){

    int len = A.length;
    int intersections = 0;

    for(int i = 0; i < len - 1; i++){

        if(A[i] <= 0){
            continue;
        }

        for(int j = i + 1; j < len; j++){

            if(A[j] <= 0){
                continue;       
            }

            if(abs((A[i] - A[j]) <= j - i) && (j - i <= A[i] + A[j])){
                intersections ++;
            }
        }
    }

    return intersections;
}
于 2013-04-24T16:19:08.790 回答