计算相交圆盘数量的算法

Java 2*100%.

result 被声明为 long 类型，用于处理 Codility 没有测试过的情况，即在一个点上有 50k*50k 个交叉点。

class Solution {
    public int solution(int[] A) {

        int[] westEnding = new int[A.length];
        int[] eastEnding = new int[A.length];

        for (int i=0; i<A.length; i++) {
            if (i-A[i]>=0) eastEnding[i-A[i]]++; else eastEnding[0]++;
            if ((long)i+A[i]<A.length) westEnding[i+A[i]]++; else westEnding[A.length-1]++;
        }

        long result = 0; //long to contain the case of 50k*50k. codility doesn't test for this.
        int wests = 0;
        int easts = 0;
        for (int i=0; i<A.length; i++) {

            int balance = easts*wests; //these are calculated elsewhere

            wests++;
            easts+=eastEnding[i];

            result += (long) easts*wests - balance - 1; // 1 stands for the self-intersection
            if (result>10000000) return -1;

            easts--;
            wests-= westEnding[i];
        }

        return (int) result;
    }
}

这是我的JavaScript解决方案，基于此线程中的其他解决方案，但使用了其他语言实现。

function solution(A) {
    let circleEndpoints = [];

    for(const [index, num] of Object.entries(A)) {
        circleEndpoints.push([parseInt(index)-num, true]);
        circleEndpoints.push([parseInt(index)+num, false]);
    }

    circleEndpoints = circleEndpoints.sort(([a, openA], [b, openB]) => {
        if(a == b) return openA ? -1 : 1;
        return a - b;
    });

    let openCircles = 0;
    let intersections = 0;

    for(const [endpoint, opening] of circleEndpoints) {
        if(opening) {
            intersections += openCircles;
            openCircles ++;
        } else {
            openCircles --;
        }
        if(intersections > 10000000) return -1;
    }

    return intersections;
}

Swift 4 解决方案100％（Codility不会检查此解决方案的最坏情况）

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var count = 0
    let sortedA = A.sorted(by: >)
    if sortedA.isEmpty{ return 0 }
    let maxVal = sortedA[0]

    for i in 0..<A.count{
        let maxIndex = min(i + A[i] + maxVal + 1,A.count)
        for j in i + 1..<maxIndex{
            if j - A[j] <= i + A[i]{
                count += 1
            }
        }

        if count > 10_000_000{
            return -1
        }
    }

    return count
}

count = 0
for (int i = 0; i < N; i++) {
  for (int j = i+1; j < N; j++) {
    if (i + A[i] >= j - A[j]) count++;
  }
}

它的时间复杂度是O(N^2)，所以速度相对较慢，但它能够正常工作。

可能非常快。O(N)。但你需要检查一下。在Codility上达到100%。 主要思想： 1. 在表的任何点，都有一定数量的圆被“打开”，直到圆的右边缘，假设为“o”。 2. 因此，在该点的圆中，有（o-1-used）个可能的配对。 “used”表示已处理并计算其配对的圆。

  public int solution(int[] A) { 
    final int N = A.length;
    final int M = N + 2;
    int[] left  = new int[M]; // values of nb of "left"  edges of the circles in that point
    int[] sleft = new int[M]; // prefix sum of left[]
    int il, ir;               // index of the "left" and of the "right" edge of the circle

    for (int i = 0; i < N; i++) { // counting left edges
      il = tl(i, A);
      left[il]++;
    }

    sleft[0] = left[0];
    for (int i = 1; i < M; i++) {// counting prefix sums for future use
      sleft[i]=sleft[i-1]+left[i];
    }
    int o, pairs, total_p = 0, total_used=0;
    for (int i = 0; i < N; i++) { // counting pairs
      ir = tr(i, A, M);
      o  = sleft[ir];                // nb of open till right edge
      pairs  = o -1 - total_used;
      total_used++;
      total_p += pairs;
    }
    if(total_p > 10000000){
      total_p = -1;
    }
    return total_p;
  }

    private int tl(int i, int[] A){
    int tl = i - A[i]; // index of "begin" of the circle
      if (tl < 0) {
        tl = 0;
      } else {
        tl = i - A[i] + 1;
      }
    return tl;
  }
  int tr(int i, int[] A, int M){
    int tr;           // index of "end" of the circle
      if (Integer.MAX_VALUE - i < A[i] || i + A[i] >= M - 1) {
        tr = M - 1;
      } else {
        tr = i + A[i] + 1;
      }
      return tr;
  }

所以，我在Scala中做了这个测试，现在想在这里分享我的例子。我的解决思路是：

提取数组中每个位置左右的界限。

A[0] = 1 --> (0-1, 0+1) = A0(-1, 1)
A[1] = 5 --> (1-5, 1+5) = A1(-4, 6)
A[2] = 2 --> (2-2, 2+2) = A2(0, 4)
A[3] = 1 --> (3-1, 3+1) = A3(2, 4)
A[4] = 4 --> (4-4, 4+4) = A4(0, 8)
A[5] = 0 --> (5-0, 5+0) = A5(5, 5)

检查任意两个位置之间是否存在交叉。

(A0_0 >= A1_0 AND A0_0 <= A1_1) OR // intersection
(A0_1 >= A1_0 AND A0_1 <= A1_1) OR // intersection
(A0_0 <= A1_0 AND A0_1 >= A1_1)    // one circle contain inside the other

如果这两个检查中有任何一个为真，则计算一个交点。

object NumberOfDiscIntersections {
  def solution(a: Array[Int]): Int = {
    var count: Long = 0
    for (posI: Long <- 0L until a.size) {
      for (posJ <- (posI + 1) until a.size) {
        val tupleI = (posI - a(posI.toInt), posI + a(posI.toInt))
        val tupleJ = (posJ - a(posJ.toInt), posJ + a(posJ.toInt))
        if ((tupleI._1 >= tupleJ._1 && tupleI._1 <= tupleJ._2) ||
          (tupleI._2 >= tupleJ._1 && tupleI._2 <= tupleJ._2) ||
          (tupleI._1 <= tupleJ._1 && tupleI._2 >= tupleJ._2)) {
          count += 1
        }
      }
    }
    count.toInt
  }
}

这是一份在Codility得分100/100的Ruby解决方案。我现在发布它是因为我发现已经发布的Ruby答案难以理解。

def solution(a)
    end_points = []
    a.each_with_index do |ai, i|
        end_points << [i - ai, i + ai]
    end
    end_points = end_points.sort_by { |points| points[0]}

    intersecting_pairs = 0
    end_points.each_with_index do |point, index|
        lep, hep = point
        pairs = bsearch(end_points, index, end_points.size - 1, hep)
        return -1 if 10000000 - pairs + index < intersecting_pairs
        intersecting_pairs += (pairs - index)
    end
    return intersecting_pairs
end

# This method returns the maximally appropriate position
# where the higher end-point may have been inserted.
def bsearch(a, l, u, x)
    if l == u
        if x >= a[u][0]
            return u
        else
            return l - 1 
        end
    end
    mid = (l + u)/2

    # Notice that we are searching in higher range
    # even if we have found equality.
    if a[mid][0] <= x
        return bsearch(a, mid+1, u, x)
    else
        return bsearch(a, l, mid, x)
    end
end

基于这个视频https://www.youtube.com/watch?v=HV8tzIiidSw，JavaScript解决方案得分100/100。

function sortArray(A) {
    return A.sort((a, b) => a - b)
}

function getDiskPoints(A) {
    const diskStarPoint = []
    const diskEndPoint = []
    for(i = 0; i < A.length; i++) {
        diskStarPoint.push(i - A[i])
        diskEndPoint.push(i + A[i])
    }
    return {
        diskStarPoint: sortArray(diskStarPoint),
        diskEndPoint: sortArray(diskEndPoint)
    };
}

function solution(A) {
    const { diskStarPoint, diskEndPoint } = getDiskPoints(A)
    let index = 0;
    let openDisks = 0;
    let intersections = 0;
    for(i = 0; i < diskStarPoint.length; i++) {
      while(diskStarPoint[i] > diskEndPoint[index]) {
        openDisks--
        index++
      }
      intersections += openDisks
      openDisks++
    }
    return intersections > 10000000 ? -1 : intersections
}

这里已经有很多好的答案，包括被接受答案的很好的解释。然而，我想指出Python语言实现细节方面的一个小观察。

最初，我提出了下面所示的解决方案。我期望得到O(N*log(N))的时间复杂度，因为我们有一个单独的for循环，其中每个迭代执行最多需要log(N)的二分查找。

def solution(a):
    import bisect
    if len(a) <= 1:
        return 0
    cuts = [(c - r, c + r) for c, r in enumerate(a)]
    cuts.sort(key=lambda pair: pair[0])
    lefts, rights = zip(*cuts)
    n = len(cuts)
    total = 0
    for i in range(n):
        r = rights[i]
        pos = bisect.bisect_right(lefts[i+1:], r)
        total += pos
        if total > 10e6:
            return -1
    return total

然而，我得到了 O(N**2) 和超时失败。你看到问题在哪里了吗？没错，就是这行代码：

pos = bisect.bisect_right(lefts[i+1:], r)

在这行代码中，你实际上是 复制 原始列表并将其传递到二分查找函数中，这完全破坏了所提出解决方案的效率！它使您的代码更加简洁（即，您不需要编写 pos - i - 1），但严重削弱了性能。因此，如上所示，解决方案应为：

def solution(a):
    import bisect
    if len(a) <= 1:
        return 0
    cuts = [(c - r, c + r) for c, r in enumerate(a)]
    cuts.sort(key=lambda pair: pair[0])
    lefts, rights = zip(*cuts)
    n = len(cuts)
    total = 0
    for i in range(n):
        r = rights[i]
        pos = bisect.bisect_right(lefts, r)
        total += (pos - i - 1)
        if total > 10e6:
            return -1
    return total

似乎有时候人们过于热衷于进行切片和复制，因为Python让这些操作变得非常容易 :) 对我来说，这可能不是一个很好的见解，但这是一个很好的教训，提醒我在将想法和算法转化为现实解决方案时要更加注意这些“技术”细节。

我知道这是一个老问题，但它仍然在codility上活跃。

    private int solution(int[] A)
    {
        int openedCircles = 0;
        int intersectCount = 0;

我们需要带有起始和结束值的圆。为此，我使用了元组。 True/False 表示我们是否添加圆的起始或结束值。

        List<Tuple<decimal, bool>> circles = new List<Tuple<decimal, bool>>();
        for(int i = 0; i < A.Length; i ++)
        {
            // Circle start value
            circles.Add(new Tuple<decimal, bool>((decimal)i - (decimal)A[i], true));

            // Circle end value
            circles.Add(new Tuple<decimal, bool>((decimal)i + (decimal)A[i], false));
        }

按照它们的值对“圆”进行排序。 如果一个圆结束的值与另一个圆开始的值相同，它应该被视为相交（因此，在同一点上，“开口”应在“关闭”之前）。

        circles = circles.OrderBy(x => x.Item1).ThenByDescending(x => x.Item2).ToList();

计数并返回计数器。

        foreach (var circle in circles)
        {
            // We are opening new circle (within existing circles)
            if(circle.Item2 == true)
            {
                intersectCount += openedCircles;

                if (intersectCount > 10000000)
                { 
                    return -1;
                }

                openedCircles++;
            }
            else
            {
                // We are closing circle
                openedCircles--;
            }
        }

        return intersectCount;
    }