计算相交圆盘数量的算法

Question

计算相交圆盘数量的算法

67

给定一个由N个整数组成的数组A，我们在二维平面上绘制N个圆盘，其中第i个圆盘的中心为(0,i)，半径为A[i]。如果第k个圆盘和第j个圆盘有至少一个公共点，则称第k个圆盘和第j个圆盘相交。

编写一个函数

int number_of_disc_intersections(int[] A);

给定一个描述N个圆盘的数组A，如上所述，返回相交圆盘对的数量。例如，给定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。

- user590076

1

算法必须高效吗？有具体的大O要求吗？我想到了一个O(n**2)的解决方案。 - vz0

2

@vz0 N 不超过 10,000,000 - Nikita Rybak

@vz0 是的，需要高效，因为它会影响总分。 - user590076

5

任何想要尝试这个挑战的人，可以参加Codility的演示挑战之一：圆盘交叉数量。他们在这篇博客文章中还有其他几个挑战。 - Defragged

4

第0和第1个圆相交的方式是什么？“公共点”是否意味着有任何重叠（比如一个圆在另一个圆内）或者只是它们的线条接触？ - dlp

44个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Enrique Arriaga · Answer 1

一个Ruby解决方案。得分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

- Remario · Answer 2

 const endpoints = [];
    A.map((val, index) => {
        endpoints.push([index - val, 'S']);
        endpoints.push([index + val, 'E']);
    });
    endpoints.sort((a, b) => {
        if (a[0] < b[0]) {
            return -1;
        }
        if (a[0] > b[0]) {
            return 1;
        }
        if (a[0] === b[0] && a[1] === 'S')
            return -1;
        else
            return 1;
    });

    let count = 0;
    let intersections = 0;
    let point = [];
    const length = endpoints.length;
    for (let i = 0; i < length; i++) {
        point = endpoints[i];
        if (point[1] === 'S') {
            count += intersections;
            intersections += 1
        } else {
            intersections -= 1;
        }
        if (intersections > 10e6)
            return -1;
    }
    return count;

- goroncy · Answer 3

你将会在Java语言下得到100/100的分数

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;

- basickarl · Answer 4

JavaScript 2016

这是 Aryabhattas 的 JavaScript 版本。我对它进行了一些改进，使它更适合 JS 并且在性能方面更加高效，还添加了注释来解释算法的作用。希望这有所帮助。

function solution(A) {
  var result = 0,
    len = A.length,
    dps = new Array(len).fill(0),
    dpe = new Array(len).fill(0),
    i,
    active = len - 1,
    s,
    e;

  for (i = 0; i < len; i++) {

    // adds to the begin array how many discs begin at the specific position given
    if (i > A[i])
      s = i - A[i];
    else
      s = 0;

    // adds to the end array the amount of discs that end at this specific position
    if (active - i > A[i])
      e = i + A[i]
    else
      e = active;

    // a disc always begins and ends somewhere, s and e are the starting and ending positions where this specific disc for the element in A at position i reside
    dps[s] += 1;
    dpe[e] += 1;
  }

  // no discs are active as the algorithm must calculate the overlaps first, then the discs can be made active, hence why it begins with 0 active
  active = 0;
  for (i = 0; i < len; i++) {
    if (dps[i] > 0) {
      // new discs has entered the zone, multiply it with the current active discs as the new discs now overlap with the older active ones
      result += active * dps[i];
      // new discs must also be counted against each other and not just the ones which were active prior
      result += dps[i] * (dps[i] - 1) / 2;
      // assignment rules
      if (10000000 < result)
        return -1;
      // add new discs to the active list that have started at this position
      active += dps[i];
    }
    // remove discs as they have ended at this position
    active -= dpe[i];
  }
  // return the result
  return result;
}

var A = [1, 5, 2, 1, 4, 0]; // should return 11
console.log(solution(A));