计算相交圆盘数量的算法

def int(a)

    event = Hash.new{|h,k| h[k] = {:start => 0, :stop => 0}}
    a.each_index {|i|
        event[i - a[i]][:start] += 1
        event[i + a[i]][:stop ] += 1
    }
    sorted_events = (event.sort_by {|index, value| index}).map! {|n| n[1]}

    past_start = 0
    intersect = 0

    sorted_events.each {|e|

        intersect += e[:start] * (e[:start]-1) / 2 +
                     e[:start] * past_start

        past_start += e[:start]
        past_start -= e[:stop]
    }
    return intersect
end

puts int [1,1]

puts int [1,5,2,1,4,0]

上述想法的Java实现：

public class DiscIntersectionCount {


public int number_of_disc_intersections(int[] A) {
    int[] leftPoints = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        leftPoints[i] = i - A[i];
    }

    Arrays.sort(leftPoints);
//      System.out.println(Arrays.toString(leftPoints));
    int count  = 0;
    for (int i = 0; i < A.length - 1; i++) {
        int rpoint = A[i] + i;

        int rrank = getRank(leftPoints, rpoint);

        //if disk has sifnificant radius, exclude own self
        if (rpoint > i) rrank -= 1;
        int rank = rrank; 
//          System.out.println(rpoint+" : "+rank);

        rank -= i;
        count += rank;
    }
    return count;

}

public int getRank(int A[], int num) {
    if (A==null || A.length == 0) return -1;        
    int mid = A.length/2;
    while ((mid >= 0) && (mid < A.length)) {

        if (A[mid] == num) return mid;

        if ((mid == 0) && (A[mid] > num)) return -1;
        if ((mid == (A.length - 1)) && (A[mid] < num)) return A.length;
        if (A[mid] < num && A[mid + 1] >= num) return mid + 1;
        if (A[mid] > num && A[mid - 1] <= num) return mid - 1;

        if (A[mid] < num) mid = (mid + A.length)/2;
        else  mid = (mid)/2;

    }

    return -1;
}

public static void main(String[] args) {
    DiscIntersectionCount d = new DiscIntersectionCount();
    int[] A = 
        //{1,5,2,1,4,0}
        //{0,0,0,0,0,0}
    //  {1,1,2}
    {3}
     ;
    int count = d.number_of_disc_intersections(A);
    System.out.println(count);
}
}

如果你在纸上画这些圆盘，你可以直观地认为它们是按每个圆盘的左端排序的。对于每个圆盘，看看右端延伸到其他圆盘的程度，也就是与其他圆盘的左端相交并停止检查。这种停止可以节省我们在O(n * n)最简单解决方案中所花费的时间，而是得到类似于O(n*log(n))的东西。虽然不像一些O(n)解决方案那样高效，但它是一个简单易懂的代码，足够有效地通过Codility提交100%的测试。在解决这个问题时，我受到了noisyboiler和GnomeDePlume的帖子的启发。

这种语言是Javascript。

function solution(A) {

    //for each disk, create an array of objects containing left and right ends, then sort it by the left end. 
    const B = A.map((a, i) => ({ left: i - a, right: i + a })).sort((a, b) => a.left - b.left)
    let count = 0
    //index i is the disk we are testing intersection with any disc j
    for (let i = 0; i < B.length - 1; i++) {
        for (let j = i + 1; j < B.length; j++) {
            if (B[i].right >= B[j].left) {
                count++;
                //this is just an explicit condition for the codility task
                if (count > 10000000) return -1
            }
            else break;
            //since the array is sorted by the left ends, we know that we won't find any disk that the right side of disc i would reach
        }
    }
    return count
}

#include <stdio.h>
#include <stdlib.h>
void sortPairs(int bounds[], int len){
    int i,j, temp;
    for(i=0;i<(len-1);i++){
        for(j=i+1;j<len;j++){
            if(bounds[i] > bounds[j]){
                temp = bounds[i];
                bounds[i] = bounds[j];
                bounds[j] = temp;
                temp = bounds[i+len];
                bounds[i+len] = bounds[j+len];
                bounds[j+len] = temp;
            }
        }
    }
}
int adjacentPointPairsCount(int a[], int len){
    int count=0,i,j;
    int *bounds;
    if(len<2) {
        goto toend;
    }
    bounds = malloc(sizeof(int)*len *2);
    for(i=0; i< len; i++){
        bounds[i] = i-a[i];
        bounds[i+len] = i+a[i];
    }
    sortPairs(bounds, len);
    for(i=0;i<len;i++){
        int currentBound = bounds[i+len];
        for(j=i+1;a[j]<=currentBound;j++){
            if(count>100000){
                count=-1;
                goto toend;
            }
            count++;
        }     
    }
toend:
    free(bounds);
    return count;   
}

由于Codility仅支持Go v1.4，因此我们必须手动实现Sorter接口来对2元组数组进行排序，这就是为什么使用golang solution的原因。

package solution

// you can also use imports, for example:
// import "fmt"
import "sort"

// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")

type Circle struct {
    left, right int
}

type CircleSorter []*Circle

func (cs CircleSorter) Len() int {
    return len(cs)
}

func (cs CircleSorter) Swap(i, j int) {
    cs[i], cs[j] = cs[j], cs[i]
}

func (cs CircleSorter) Less(i, j int) bool {
    return cs[i].left < cs[j].left
}

func BiSecRight(data []*Circle, target int) int {
    return sort.Search(len(data), func(i int) bool {
        return data[i].left > target
    })
}

func Solution(A []int) int {
    data := make([]*Circle, len(A))
    for i := 0; i < len(A); i++ {
        data[i] = &Circle{
            left:  i - A[i],
            right: i + A[i],
        }
    }

    sort.Sort(CircleSorter(data))

    count := 0

    for i, v := range data {
        count += BiSecRight(data, v.right) - 1 - i
    }

    if count > 10000000 {
        count = -1
    }

    return count
}

C#解决方案100/100

using System.Linq;

class Solution
{
    private struct Interval
    {
        public Interval(long @from, long to)
        {
            From = @from;
            To = to;
        }

        public long From { get; }
        public long To { get; }
    }

    public int solution(int[] A)
    {
        int result = 0;

        Interval[] intervals = A.Select((value, i) =>
        {
            long iL = i;
            return new Interval(iL - value, iL + value);
        })
        .OrderBy(x => x.From)
        .ToArray();

        for (int i = 0; i < intervals.Length; i++)
        {
            for (int j = i + 1; j < intervals.Length && intervals[j].From <= intervals[i].To; j++)
                result++;

            if (result > 10000000)
                return -1;
        }

        return result;
    }
}

这是我所做的... 它提供了100%的性能和93%的正确性（因为一个测试“算术溢出测试”失败了）。

public static int NumberOfDiscIntersections(int[] A)
    {
        int[] leftEdges = new int[A.Length];
        int[] rightEdges = new int[A.Length];
        int openDisc = 0;
        int intersect = 0;
        int leftEdgeIndex = 0;
        for (int i = 0; i < A.Length; i++)
        {
            leftEdges[i] = i - A[i];
            rightEdges[i] = i + A[i];
        }
        Array.Sort(leftEdges);
        Array.Sort(rightEdges);

        for (int j = 0; j < rightEdges.Length; j++)
        {
            for (int i = leftEdgeIndex; i < leftEdges.Length; i++)
            {
                if (leftEdges[i] <= rightEdges[j])
                {
                    intersect += openDisc;
                    openDisc += 1;
                    leftEdgeIndex += 1;
                }
                else
                {
                    openDisc -= 1;
                    break;
                }
                if (intersect > 10000000) return -1;
            }
            if(leftEdgeIndex == leftEdges.Length)
            {
                break; //All Left Edges are opened, So all Intersect calculated
            }                
        }
        return intersect;
    }

这是一个O(N)时间复杂度和O(N)空间复杂度的解决方案。不需要排序。

这个解决方案在Codility上得分100%。

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  let totalUniquePairs = 0;
  
  if (A.length === 0) return 0;
  
  // array contain counts of how many circles begin at that index
  const opens = new Array(A.length).fill(0);
  // array containg counts of how many circles stop at that index
  const closes = new Array(A.length).fill(0);
  
  // populate the open/closes
  for (let i = 0; i < A.length; ++i) {
      const radius = A[i];
      // keep this within the bounds of the array
      const opensAt = Math.max(0, i - radius);
      const closesAt = Math.min(A.length - 1, i + radius);
      ++closes[closesAt];
      ++opens[opensAt];
  }

  
  // operate in sort of a stack fashion
  let overlapping = 0;
  for (let i = 0; i < A.length; ++i) {
      const opening = opens[i];
      const closing = closes[i];
      overlapping += opening;
      
      if (closing <= 0) continue; // no closing, no new pairs

      // naive way
      // for (let j = 0; j < closing; ++j) {
      //     // overlapping - 1 = possible unique pairs here
      //     totalUniquePairs += overlapping - 1;
      //     if (totalUniquePairs > 10000000) return -1;
      //     overlapping -= 1;
      // }
      
      // optimized way
      // summation pattern from 1 to some number k
      // closes = 3 => totalUniquePairs += (overlapping - 1) + (overlapping - 2) + (overlapping - 3);
      // ^ can be simplified as totalUniquePairs += (overlapping * k) - (k * (k + 1) / 2);
      // https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF
      totalUniquePairs += (overlapping * closing) - (closing * (closing + 1) / 2);
      if (totalUniquePairs > 10000000) return -1;
      overlapping -= closing;
  }
  
  
  return totalUniquePairs;
}

• 在此索引i处有多少圆打开？打开数组处理此
• 在此索引i处有多少圆关闭？关闭数组处理此

Javascript解决方案，时间复杂度为O(N*log(N))，空间复杂度为O(N)。

function solution(A) {
  const start = [];
  const end = [];

  A.forEach((radius, index) => {
    start.push(index - radius);
    end.push(index + radius);
  });

  start.sort((a, b) => a - b);
  end.sort((a, b) => a - b);

  let intersections = 0;
  let open = 0;

  let i = 0;
  let j = 0;

  while (i < start.length) {
    if (start[i] <= end[j]) {
      intersections += open;
      if (intersections > 10000000) {
        return -1;
      }
      open++;
      i++;
    } else {
      open--;
      j++;
    }
  }

  return intersections;
}

enter code here

与其他答案（C++）类似，但略有不同，简短且解释清楚。在空间和时间上是线性的，并且在Codility上达到了100%。

让我们首先定义以下规则：

1. 如果你在点X处打开N个圆盘（即N个圆盘从最左侧位置索引为X开始），那么所有这些圆盘都会相交。我们不能重复计算交叉点（圆盘1与2相交，圆盘2与1相交=1个交叉点，而不是2个）。因此，计算交叉点的公式是：N（N-1）/ 2（可以通过手动检查轻松验证）。
2. 在点X + 1处，你又打开了一组M个圆盘。我们使用第1点的公式，并且由于我们没有关闭任何之前的圆盘，所以我们要添加M * N个交叉点（同样可以通过手动检查轻松验证）。
3. 如果在X + 1处我们关闭了C个圆盘，那么第2点的公式将是M *（N - C），其中N - C是在点X + 1处已经打开的圆盘数量（不包括新的圆盘 - M）。

    int solution(vector<int> &A) {
        // count start/end points at each position
        std::vector<size_t> starts(A.size(), 0);
        std::vector<size_t> ends(A.size(), 0);
        for (size_t idx = 0; idx < A.size(); ++idx)
        {
            // make sure not to have overflow here
            size_t s = std::max<int>(0, idx - A[idx]);
            size_t e = std::min<size_t>(A.size() - 1, idx + A[idx]);
        
            ++starts[s];
            ++ends[e];
        }
        // starts[idx] is a counter which indicates how many discs have their uttermost left point at idx
        // ends[idx] is a counter which indicates how many discs have their uttermost right point at idx

        // loop over lines and count intersections (make sure no overflow)
        unsigned long int openDiscs = 0;
        unsigned long int intersections = 0;
        for (size_t idx = 0; idx < A.size(); ++idx)
        {
            // intersections due to newly opened discs (point 1)
            intersections += starts[idx] * (starts[idx] - 1) / 2;
        
            // intersections due to previously opened discs (point 2, 3)
            intersections += openDiscs * starts[idx];
        
            // update open discs
            openDiscs += starts[idx] - ends[idx];
        
            if (intersections > 10000000) return -1;
        }
    
        return intersections;
    }