给定A整数的N数组，我们在2D平面上绘制N圆盘，这样第i个圆盘的中心位于(0,i)，半径为A[i]。如果第k个和第j个盘具有至少一个公共点，我们说第k个盘和第j个盘相交。
写一个函数
int number_of_disc_intersections(int[] A);
如上所述给出了描述A光盘的数组N，返回相交光盘对的数量。例如，给定N=6和
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0
共有11对交叉盘：
0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th
所以函数应该返回11.如果相交对的数量超过10,000,000，函数应该返回-1。该函数可以假设N不超过10,000,000。
所以你想找到间隔[i-A[i], i+A[i]]的交叉点数。
维护一个包含i-A[i]的排序数组（称之为X）（还有一些额外的空间，其中有i+A[i]值）。
现在走到阵列X，从最左边的间隔开始（即最小的i-A[i]）。
对于当前间隔，进行二分搜索以查看间隔的右端点（即i+A[i]）将去向何处（称为等级）。现在您知道它与左侧的所有元素相交。
增加一个具有等级的计数器并减去当前位置（假设一个被索引），因为我们不想重复计算间隔和自交叉。
O（nlogn）时间，O（n）空间。
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)非常慢，但它的工作原理。
这是一种红宝石解决方案，在编码方面得分为100/100。我现在发布它，因为我发现很难按照已经发布的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
100/100 c＃
class Solution
{
class Interval
{
public long Left;
public long Right;
}
public int solution(int[] A)
{
if (A == null || A.Length < 1)
{
return 0;
}
var itervals = new Interval[A.Length];
for (int i = 0; i < A.Length; i++)
{
// use long to avoid data overflow (eg. int.MaxValue + 1)
long radius = A[i];
itervals[i] = new Interval()
{
Left = i - radius,
Right = i + radius
};
}
itervals = itervals.OrderBy(i => i.Left).ToArray();
int result = 0;
for (int i = 0; i < itervals.Length; i++)
{
var right = itervals[i].Right;
for (int j = i + 1; j < itervals.Length && itervals[j].Left <= right; j++)
{
result++;
if (result > 10000000)
{
return -1;
}
}
}
return result;
}
}
可能非常快。上）。但你需要检查一下。 100％的Codility。主要思想：1。在桌子的任何一点，有多个圆圈“打开”直到圆圈的右边缘，让我们说“o”。因此，该点的圆圈有（o-1次使用的）可能的对。 “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;
}
这在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));
}
}
}
感谢Falk的好主意！这是一个利用稀疏性的ruby实现。
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]
#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;
}
以上在Java中实现的Idea：
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);
}
}
以下是关于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 ++代码。伙计们，你能详细说明你在这做什么吗？
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;
}
}
O（N）复杂度和O（N）内存解决方案。
private static int Intersections(int[] a)
{
int result = 0;
int[] dps = new int[a.length];
int[] dpe = new int[a.length];
for (int i = 0, t = a.length - 1; i < a.length; i++)
{
int s = i > a[i]? i - a[i]: 0;
int e = t - i > a[i]? i + a[i]: t;
dps[s]++;
dpe[e]++;
}
int t = 0;
for (int i = 0; i < a.length; i++)
{
if (dps[i] > 0)
{
result += t * dps[i];
result += dps[i] * (dps[i] - 1) / 2;
if (10000000 < result) return -1;
t += dps[i];
}
t -= dpe[i];
}
return result;
}
在Codility 100％得分。
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;
}
这是一个两遍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;
}
我在斯威夫特的回答;获得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
}
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％。
def solution(a)
# write your code in Ruby 2.2
open = Hash.new
close = Hash.new
(0..(a.length-1)).each do |c|
r = a[c]
open[ c-r ] ? open[ c-r ]+=1 : open[ c-r ]=1
close[ c+r ] ? close[ c+r ]+=1 : close[ c+r ]=1
end
open_now = 0
intersections = 0
open.merge(close).keys.sort.each do |v|
intersections += (open[v]||0)*open_now
open_now += (open[v]||0) - (close[v]||0)
if(open[v]||0)>1
# sum the intersections of only newly open discs
intersections += (open[v]*(open[v]-1))/2
return -1 if intersections > 10000000
end
end
intersections
end
C＃100/100具有O(N*log(N))时间复杂度和O(N)空间复杂度。
主要观点：
true表示“打开”，false表示“关闭”一个间隔。_
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;
}
这里有很多很棒的答案，包括接受答案的重要解释。但是，我想指出一个关于Python语言中实现细节的小观察。
最初，我想出了下面显示的解决方案。当我们有一个O(N*log(N))迭代的单循环时，我期望得到N时间复杂度，并且每次迭代执行最多需要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允许你这么容易地做到:)可能不是一个很好的洞察力，但对我来说，这是一个很好的教训，更加关注这些“技术”时刻将想法和算法转换为真实的解决方案。
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
}
下面是@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％的分数。
这是我在Python中的干净解决方案（不导入库）。该逻辑可以适用于任何其他编程语言。
我得到100％的Codility - 时间：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
好吧，我将FalkHüffner的想法改编为c ++，并改变了范围。与上面所写的相反，没有必要超出数组的范围（无论数值有多大）。在Codility上，这段代码收到了100％。谢谢Falk的好主意！
int number_of_disc_intersections ( const vector<int> &A ) {
int sum=0;
vector<int> start(A.size(),0);
vector<int> end(A.size(),0);
for (unsigned int i=0;i<A.size();i++){
if ((int)i<A[i]) start[0]++;
else start[i-A[i]]++;
if (i+A[i]>=A.size()) end[A.size()-1]++;
else end[i+A[i]]++;
}
int active=0;
for (unsigned int i=0;i<A.size();i++){
sum+=active*start[i]+(start[i]*(start[i]-1))/2;
if (sum>10000000) return -1;
active+=start[i]-end[i];
}
return sum;
}
您将获得100/100的Java语言以下解决方案
if (A == null || A.length < 2) {
return 0;
}
int[] B = Arrays.copyOf(A, A.length);
Arrays.sort(B);
int biggest = B[A.length - 1];
int intersections = 0;
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length; j++) {
if (j - biggest > i + A[i]) {
break;
}
if (j - A[j] <= i + A[i]) {
intersections++;
}
if (intersections > 10000000) {
return -1;
}
}
}
return intersections;
这甚至可以在线性时间内完成。实际上，如果忽略每个点上只有一个区间，并将其视为一组间隔的起点和终点这一事实，就会变得更容易。然后，您可以从左侧扫描它（为简单起见，Python代码）：
from collections import defaultdict
a = [1, 5, 2, 1, 4, 0]
start = defaultdict(int)
stop = defaultdict(int)
for i in range(len(a)):
start[i - a[i]] += 1
stop[i + a[i]] += 1
active = 0
intersections = 0
for i in range(-len(a), len(a)):
intersections += active * start[i] + (start[i] * (start[i] - 1)) / 2
active += start[i]
active -= stop[i]
print intersections
这是一个O（N）时间，O（N）空间算法需要在数组上运行3次并且没有排序，verified scoring 100%：
你对成对的光盘很感兴趣。每对涉及一个盘的一侧和另一盘的另一侧。因此，如果我们处理每张光盘的一面，我们就不会有重复对。让我们左右两边调用（我在思考它时旋转了空间）。
重叠是由于右侧直接在中心处重叠另一个盘（因此对等于半径而关心阵列长度）或者由于在最右边存在的左侧的数量。
因此，我们创建一个数组，其中包含每个点的左侧数，然后它是一个简单的总和。
C代码：
int solution(int A[], int N) {
int C[N];
int a, S=0, t=0;
// Mark left and middle of disks
for (int i=0; i<N; i++) {
C[i] = -1;
a = A[i];
if (a>=i) {
C[0]++;
} else {
C[i-a]++;
}
}
// Sum of left side of disks at location
for (int i=0; i<N; i++) {
t += C[i];
C[i] = t;
}
// Count pairs, right side only:
// 1. overlaps based on disk size
// 2. overlaps based on disks but not centers
for (int i=0; i<N; i++) {
a = A[i];
S += ((a<N-i) ? a: N-i-1);
if (i != N-1) {
S += C[((a<N-i) ? i+a: N-1)];
}
if (S>10000000) return -1;
}
return S;
}
Python 100/100（测试）关于codility，具有O（nlogn）时间和O（n）空间。
这是@noisyboiler的@Aryabhatta方法的python实现，带有注释和示例。完全归功于原作者，任何错误/不良措辞完全是我的错。
from bisect import bisect_right
def number_of_disc_intersections(A):
pairs = 0
# create an array of tuples, each containing the start and end indices of a disk
# some indices may be less than 0 or greater than len(A), this is fine!
# sort the array by the first entry of each tuple: the disk start indices
intervals = sorted( [(i-A[i], i+A[i]) for i in range(len(A))] )
# create an array of starting indices using tuples in intervals
starts = [i[0] for i in intervals]
# for each disk in order of the *starting* position of the disk, not the centre
for i in range(len(starts)):
# find the end position of that disk from the array of tuples
disk_end = intervals[i][1]
# find the index of the rightmost value less than or equal to the interval-end
# this finds the number of disks that have started before disk i ends
count = bisect_right(starts, disk_end )
# subtract current position to exclude previous matches
# this bit seemed 'magic' to me, so I think of it like this...
# for disk i, i disks that start to the left have already been dealt with
# subtract i from count to prevent double counting
# subtract one more to prevent counting the disk itsself
count -= (i+1)
pairs += count
if pairs > 10000000:
return -1
return pairs
工作示例：给定[3,0,1,6]，磁盘半径如下所示：
disk0 ------- start= -3, end= 3
disk1 . start= 1, end= 1
disk2 --- start= 1, end= 3
disk3 ------------- start= -3, end= 9
index 3210123456789 (digits left of zero are -ve)
intervals = [(-3, 3), (-3, 9), (1, 1), (1,3)]
starts = [-3, -3, 1, 1]
the loop order will be: disk0, disk3, disk1, disk2
0th loop:
by the end of disk0, 4 disks have started
one of which is disk0 itself
none of which could have already been counted
so add 3
1st loop:
by the end of disk3, 4 disks have started
one of which is disk3 itself
one of which has already started to the left so is either counted OR would not overlap
so add 2
2nd loop:
by the end of disk1, 4 disks have started
one of which is disk1 itself
two of which have already started to the left so are either counted OR would not overlap
so add 1
3rd loop:
by the end of disk2, 4 disks have started
one of which is disk2 itself
two of which have already started to the left so are either counted OR would not overlap
so add 0
pairs = 6
to check: these are (0,1), (0,2), (0,2), (1,2), (1,3), (2,3),
我用这个C ++实现得到100分中的100分：
#include <map>
#include <algorithm>
inline bool mySortFunction(pair<int,int> p1, pair<int,int> p2)
{
return ( p1.first < p2.first );
}
int number_of_disc_intersections ( const vector<int> &A ) {
int i, size = A.size();
if ( size <= 1 ) return 0;
// Compute lower boundary of all discs and sort them in ascending order
vector< pair<int,int> > lowBounds(size);
for(i=0; i<size; i++) lowBounds[i] = pair<int,int>(i-A[i],i+A[i]);
sort(lowBounds.begin(), lowBounds.end(), mySortFunction);
// Browse discs
int nbIntersect = 0;
for(i=0; i<size; i++)
{
int curBound = lowBounds[i].second;
for(int j=i+1; j<size && lowBounds[j].first<=curBound; j++)
{
nbIntersect++;
// Maximal number of intersections
if ( nbIntersect > 10000000 ) return -1;
}
}
return nbIntersect;
}
一个Python答案
from bisect import bisect_right
def number_of_disc_intersections(li):
pairs = 0
# treat as a series of intervals on the y axis at x=0
intervals = sorted( [(i-li[i], i+li[i]) for i in range(len(li))] )
# do this by creating a list of start points of each interval
starts = [i[0] for i in intervals]
for i in range(len(starts)):
# find the index of the rightmost value less than or equal to the interval-end
count = bisect_right(starts, intervals[i][1])
# subtract current position to exclude previous matches, and subtract self
count -= (i+1)
pairs += count
if pairs > 10000000:
return -1
return pairs
Java 2 * 100％。
result被宣布为长期以来一个案件的密集性没有测试，即一点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;
}
}