计算交叉盘数的算法

Question

给定一个整数数组A,N我们N在2D平面中绘制光盘,使得第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.

Answer 1

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;
}

Answer 2

所以你想找到间隔的交叉点数[i-A[i], i+A[i]].

维护一个包含i-A[i](也有一些额外空间,其中包含值)的排序数组(称为X i+A[i]).

现在从最左边的间隔(即最小的i-A[i])开始走数组X.

对于当前间隔,执行二进制搜索以查看间隔(即i+A[i])的右端点将在何处(称为等级).现在您知道它与左侧的所有元素相交.

增加一个具有等级的计数器并减去当前位置(假设一个被索引),因为我们不想重复计算间隔和自交叉.

O(nlogn)时间,O(n)空间.

Answer 3

好吧,我将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;
}

Answer 4

这甚至可以在线性时间内完成.实际上,如果忽略每个点上只有一个区间,并将其视为一组间隔的起点和终点这一事实,就会变得更容易.然后,您可以从左侧扫描它(为简单起见,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

Answer 5

这是一个O(N)时间,O(N)空间算法需要在阵列上运行3次并且没有排序,验证得分为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;
}

Answer 6

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),    

Answer 7

我用这个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;
}