计算相交圆盘数量的算法

在Codility中获得100%的分数。

这是Толя solution的C#适配版本：

    public int solution(int[] A)
    {
        long result = 0;
        Dictionary<long, int> dps = new Dictionary<long, int>();
        Dictionary<long, int> dpe = new Dictionary<long, int>();

        for (int i = 0; i < A.Length; i++)
        {
            Inc(dps, Math.Max(0, i - A[i]));
            Inc(dpe, Math.Min(A.Length - 1, i + A[i]));
        }

        long t = 0;
        for (int i = 0; i < A.Length; i++)
        {
            int value;
            if (dps.TryGetValue(i, out value))
            {
                result += t * value;
                result += value * (value - 1) / 2;
                t += value;
                if (result > 10000000)
                    return -1;
            }
            dpe.TryGetValue(i, out value);
            t -= value;
        }

        return (int)result;
    }

    private static void Inc(Dictionary<long, int> values, long index)
    {
        int value;
        values.TryGetValue(index, out value);
        values[index] = ++value;
    }

根据Aryabhatta（二分查找解决方案）的描述，实现了一个100/100的C#程序。

using System;

class Solution {
    public int solution(int[] A)
    {
        return IntersectingDiscs.Execute(A);
    }
}

class IntersectingDiscs
{
    public static int Execute(int[] data)
    {
        int counter = 0;

        var intervals = Interval.GetIntervals(data);

        Array.Sort(intervals); // sort by Left value

        for (int i = 0; i < intervals.Length; i++)
        {
            counter += GetCoverage(intervals, i);

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

        return counter;
    }

    private static int GetCoverage(Interval[] intervals, int i)
    {
        var currentInterval = intervals[i];

        // search for an interval starting at currentInterval.Right

        int j = Array.BinarySearch(intervals, new Interval { Left = currentInterval.Right });

        if(j < 0)
        {
            // item not found

            j = ~j; // bitwise complement (see Array.BinarySearch documentation)

            // now j == index of the next item larger than the searched one

            j = j - 1; // set index to the previous element
        }

        while(j + 1 < intervals.Length && intervals[j].Left == intervals[j + 1].Left)
        {
            j++; // get the rightmost interval starting from currentInterval.Righ
        }

        return j - i; // reduce already processed intervals (the left side from currentInterval)
    }
}

class Interval : IComparable
{
    public long Left { get; set; }
    public long Right { get; set; }

    // Implementation of IComparable interface
    // which is used by Array.Sort().
    public int CompareTo(object obj)
    {
        // elements will be sorted by Left value

        var another = obj as Interval;

        if (this.Left < another.Left)
        {
            return -1;
        }

        if (this.Left > another.Left)
        {
            return 1;
        }

        return 0;
    }

    /// <summary>
    /// Transform array items into Intervals (eg. {1, 2, 4} -> {[-1,1], [-1,3], [-2,6]}).
    /// </summary>
    public static Interval[] GetIntervals(int[] data)
    {
        var intervals = new Interval[data.Length];

        for (int i = 0; i < data.Length; i++)
        {
            // use long to avoid data overflow (eg. int.MaxValue + 1)

            long radius = data[i];

            intervals[i] = new Interval
            {
                Left = i - radius,
                Right = i + radius
            };
        }

        return intervals;
    }
}

这是一个不需要任何库、二分查找、排序等的两遍 C++ 解决方案。

int solution(vector<int> &A) {
    #define countmax 10000000
    int count = 0;
    // init lower edge array
    vector<int> E(A.size());
    for (int i = 0; i < (int) E.size(); i++)
        E[i] = 0;
    // first pass
    // count all lower numbered discs inside this one
    // mark lower edge of each disc
    for (int i = 0; i < (int) A.size(); i++)
    {
        // if disc overlaps zero
        if (i - A[i] <= 0)
            count += i;
        // doesn't overlap zero
        else {   
            count += A[i];
            E[i - A[i]]++;
        }
        if (count > countmax)
            return -1;
    }
    // second pass
    // count higher numbered discs with edge inside this one
    for (int i = 0; i < (int) A.size(); i++)
    {
        // loop up inside this disc until top of vector
        int jend = ((int) E.size() < (long long) i + A[i] + 1 ? 
                    (int) E.size() : i + A[i] + 1);
        // count all discs with edge inside this disc
        // note: if higher disc is so big that edge is at or below 
        // this disc center, would count intersection in first pass
        for (int j = i + 1; j < jend; j++)
            count += E[j];
        if (count > countmax)
            return -1;
    }
    return count;
}

我的 Swift 答案得到了 100% 的分数。

import Glibc

struct Interval {
    let start: Int
    let end: Int
}

func bisectRight(intervals: [Interval], end: Int) -> Int {
    var pos = -1
    var startpos = 0
    var endpos = intervals.count - 1

    if intervals.count == 1 {
        if intervals[0].start < end {
            return 1
        } else {
            return 0
        }
    }

    while true {
        let currentLength = endpos - startpos

        if currentLength == 1 {
            pos = startpos
            pos += 1
            if intervals[pos].start <= end {
                pos += 1
            }
            break
        } else {
            let middle = Int(ceil( Double((endpos - startpos)) / 2.0 ))
            let middlepos = startpos + middle

            if intervals[middlepos].start <= end {
                startpos = middlepos
            } else {
                endpos = middlepos
            }
        }
    }

    return pos
}

public func solution(inout A: [Int]) -> Int {
    let N = A.count
    var nIntersections = 0

    // Create array of intervals
    var unsortedIntervals: [Interval] = []
    for i in 0 ..< N {
        let interval = Interval(start: i-A[i], end: i+A[i])
        unsortedIntervals.append(interval)
    }

    // Sort array
    let intervals = unsortedIntervals.sort {
        $0.start < $1.start
    }

    for i in 0 ..< intervals.count {
        let end = intervals[i].end

        var count = bisectRight(intervals, end: end)

        count -= (i + 1)
        nIntersections += count

        if nIntersections > Int(10E6) {
            return -1
        }
    }

    return nIntersections
}

O(N*logN) 100%/100%

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        long[] startPositionList = new long[A.length];
        long[] finishPositionList = new long[A.length];
        for (int i = 0; i < A.length; i++) {
            // (long), because otherwise number 2,147,483,647 will overflow
            startPositionList[i] = (long)i - A[i];
            finishPositionList[i] = (long)i + A[i];
        }

        Arrays.sort(startPositionList);
        Arrays.sort(finishPositionList);

        int count = 0;
        int multiplier = 0;
        int startIndex = 0;
        int finishIndex = 0;
        // After we passed through all start positions, our solution won't change, hence we can stop the loop
        while (startIndex < A.length) {
            if (startPositionList[startIndex] > finishPositionList[finishIndex]) {
                // Finish position is next smallest
                multiplier--;
                finishIndex++;
            } else {
                // Start position is next smallest or is equal to finish position
                count += multiplier;
                multiplier++;
                startIndex++;
                // There is a condition to return -1 if count is bigger than 1e7
                if (count > (int)1e7) {
                    return -1;
                }
            }
        }

        return count;
    }
}

这里是在Codility上得分100的PHP代码：

$sum=0;

//One way of cloning the A:
$start = array();
$end = array();

foreach ($A as $key=>$value)
{
$start[]=0;
$end[]=0;   
}  

for ($i=0; $i<count($A); $i++)
{
  if ($i<$A[$i]) 
  $start[0]++;
  else        
  $start[$i-$A[$i]]++;

  if ($i+$A[$i] >= count($A))   
  $end[count($A)-1]++;
  else
  $end[$i+$A[$i]]++;
}
$active=0;
for ($i=0; $i<count($A);$i++)
{
  $sum += $active*$start[$i]+($start[$i]*($start[$i]-1))/2;
  if ($sum>10000000) return -1;
  $active += $start[$i]-$end[$i];
}
return $sum;

然而我不理解这个逻辑。这只是从上面转换来的C++代码。各位，你们能详细说明一下在这里做了什么吗？

这是我的Python干净解决方案（不需要导入库）。这个逻辑可以适用于任何其他编程语言。
我在Codility中获得了100％的分数 - 时间：O（Nlog（N））-空间：O（N）
希望能对你有所帮助。

def solution(A):
  start, end = [], []
  for i, val in enumerate(A):
    start.append(i-val)
    end.append(i+val)

  start.sort()
  end.sort()

  count, currCircles, aux1, aux2 = 0, 0, 0, 0
  while aux1 != len(start) and aux2 != len(end):
    if aux1 < len(start) and start[aux1] <= end[aux2]:
      count += currCircles
      currCircles +=1
      aux1 +=1
      if currCircles > 10000000:
          return -1
    else:
      currCircles -=1
      aux2 +=1

  return count

以下是@Aryabhatta在Kotlin中所接受的答案的实现，所有的功劳都归于@Aryabhatta。

fun calculateDiscIntersections(A: Array<Int>): Int {
    val MAX_PAIRS_ALLOWED = 10_000_000L
    //calculate startX and endX for each disc
    //as y is always 0 so we don't care about it. We only need X
    val ranges = Array(A.size) { i ->
        calculateXRange(i, A[i])
    }

    //sort Xranges by the startX
    ranges.sortBy { range ->
        range.start
    }

    val starts = Array(ranges.size) {index ->
        ranges[index].start
    }

    var count = 0
    for (i in 0 until ranges.size) {
        val checkRange = ranges[i]

        //find the right most disc whose start is less than or equal to end of current disc
        val index = bisectRight(starts, checkRange.endInclusive, i)

        //the number of discs covered by this disc are:
        //count(the next disc/range ... to the last disc/range covered by given disc/range)
        //example: given disc index = 3, last covered (by given disc) disc index = 5
        //count = 5 - 3 = 2
        //because there are only 2 discs covered by given disc
        // (immediate next disc with index 4 and last covered disc at index 5)
        val intersections = (index - i)

        //because we are only considering discs intersecting/covered by a given disc to the right side
        //and ignore any discs that are intersecting on left (because previous discs have already counted those
        // when checking for their right intersects) so this calculation avoids any duplications
        count += intersections

        if (count > MAX_PAIRS_ALLOWED) {
            return -1
        }
    }

    return if (count > MAX_PAIRS_ALLOWED) {
        -1
    } else {
        count
    }
}

private fun calculateXRange(x: Int, r: Int): LongRange {
    val minX = x - r.toLong()
    val maxX = x + r.toLong()

    return LongRange(minX, maxX)
}

fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
    var start = arrayStart
    var end = array.size - 1
    var bisect = start

    while (start <= end) {
        val mid = Math.ceil((start + end) / 2.0).toInt()
        val midValue = array[mid]
        val indexAfterMid = mid + 1

        if (key >= midValue) {
            bisect = mid
        }

        if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
            break
        } else if (key < midValue) {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }

    return bisect
}

Codility Solution 得分100％。

C# 100/100，时间复杂度为O(N*log(N))，空间复杂度为O(N)。

主要思路：

1. 创建两个已排序的数组：左端点和右端点。
2. 将这些数组合并成一个布尔数组，其中true表示“打开”一个区间，false表示“关闭”一个区间。
3. 遍历布尔数组并计算打开的区间数量，将它们相加。

_

public int solution(int[] A) 
{        
    var sortedStartPoints = A.Select((value, index) => (long)index-value).OrderBy(i => i).ToArray();
    var sortedEndPoints = A.Select((value, index) => (long)index+value).OrderBy(i => i).ToArray();     

    // true - increment, false - decrement, null - stop
    var points = new bool?[2*A.Length];

    // merge arrays
    for(int s=0, e=0, p=0; p < points.Length && s < sortedStartPoints.Length; p++)
    {
        long startPoint = sortedStartPoints[s];
        long endPoint = sortedEndPoints[e];
        if(startPoint <= endPoint)
        {
            points[p] = true;
            s++;
        }
        else
        {
            points[p] = false;
            e++;
        }
    }

    int result = 0;
    int opened = 0;
    // calculate intersections
    foreach(bool? p in points.TakeWhile(_ => _.HasValue))
    {
        if(result > 10000000)
            return -1;

        if(p == true)
        {
            result += opened;
            opened++;
        }
        else
        {                
            opened--;
        }
    }

    return result;
}

这个在C#中获得了100/100分。

class CodilityDemo3
{

    public static int GetIntersections(int[] A)
    {
        if (A == null)
        {
            return 0;
        }

        int size = A.Length;

        if (size <= 1)
        {
            return 0;
        }

        List<Line> lines = new List<Line>();

        for (int i = 0; i < size; i++)
        {
            if (A[i] >= 0)
            {
                lines.Add(new Line(i - A[i], i + A[i]));
            }
        }

        lines.Sort(Line.CompareLines);
        size = lines.Count;
        int intersects = 0;

        for (int i = 0; i < size; i++)
        {
            Line ln1 = lines[i];
            for (int j = i + 1; j < size; j++)
            {
                Line ln2 = lines[j];
                if (ln2.YStart <= ln1.YEnd)
                {
                    intersects += 1;
                    if (intersects > 10000000)
                    {
                        return -1;
                    }
                }
                else
                {
                    break;
                }
            }
        }

        return intersects;
    }

}

public class Line
{
    public Line(double ystart, double yend)
    {
        YStart = ystart;
        YEnd = yend;
    }
    public double YStart { get; set; }
    public double YEnd { get; set; }

    public static int CompareLines(Line line1, Line line2)
    {
        return (line1.YStart.CompareTo(line2.YStart));

    }
}

}