반응형
교차하는 디스크 수를 계산하는 알고리즘
정수 배열 A이 주어지면 i 번째 디스크가 중심 과 반경을 갖도록 2D 평면에 디스크를 그 N립니다 . k 번째 디스크와 j 번째 디스크가 적어도 하나의 공통점을 가지고 있다면 k 번째 디스크와 j 번째 디스크가 교차한다고 말합니다.N(0,i)A[i]
함수 작성
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을 반환해야합니다. 함수는 N10,000,000을 초과하지 않는다고 가정 할 수 있습니다 .
따라서 간격의 교차점 수를 찾고 싶습니다 [i-A[i], i+A[i]].
i-A[i](또한 i+A[i]거기에 값이있는 추가 공간이 있음 )을 포함하는 정렬 된 배열 (X라고 부름)을 유지하십시오 .
이제 가장 왼쪽 간격 (즉, smallest i-A[i]) 에서 시작하여 배열 X를 걷습니다 .
현재 간격에 대해 이진 검색을 수행하여 간격의 오른쪽 끝점 (예 : i+A[i]순위)이 어디로 가는지 확인합니다. 이제 왼쪽의 모든 요소와 교차한다는 것을 알았습니다.
계수 간격과 자체 교차를 두 번 계산하지 않기를 원하므로 순위로 카운터를 늘리고 현재 위치를 뺍니다 (인덱싱 된 것으로 가정).
O (nlogn) 시간, O (n) 공간.
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;
}
글쎄, 나는 Falk Hü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;
}
이것은 선형 시간으로도 가능합니다. 실제로 각 지점에 정확히 하나의 간격이 있다는 사실을 무시하고 간격의 시작 및 끝점 집합으로 처리하면 더 쉬워집니다. 그런 다음 왼쪽에서 스캔 할 수 있습니다 (간결성을 위해 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 번 실행되고 정렬없이 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;
}
O (nlogn) 시간과 O (n) 공간을 사용하여 Python 100/100 (테스트 됨).
다음은 주석 및 예제와 함께 @Aryabhatta의 메서드에 대한 @noisyboiler의 파이썬 구현입니다. 원저자에 대한 전적인 신용, 오류 / 잘못된 문구는 전적으로 내 잘못입니다.
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;
}
파이썬 답변
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
자바 2 * 100 %.
result 케이스 codility가 테스트하지 않는 한, 즉 한 지점에서 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;
}
}
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)매우 느린 때문에,하지만 작동합니다.
이것은 codility에서 100/100 점을 얻은 루비 솔루션입니다. 이미 게시 된 루비 답변을 따르기가 어렵 기 때문에 지금 게시하고 있습니다.
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;
}
}
아마도 매우 빠릅니다. 의 위에). 그러나 당신은 그것을 확인해야합니다. Codility 100 %. 주요 아이디어 : 1. 테이블의 어느 지점에서나 원의 오른쪽 가장자리까지 "열린"원의 수가 있습니다. "o"라고 말합시다. 2. 따라서 그 지점에서 원에 대해 가능한 쌍 (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;
}
받아 들여진 답변의 훌륭한 설명을 포함하여 이미 여기에 많은 훌륭한 답변이 있습니다. 그러나 저는 파이썬 언어의 구현 세부 사항에 대한 작은 관찰을 지적하고 싶었습니다.
원래 아래에 표시된 해결책을 찾았습니다. 반복 O(N*log(N))이 포함 된 단일 for 루프가 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
파이썬이 그렇게 쉽게 할 수 있기 때문에 때때로 슬라이스와 카피를 만드는 것에 너무 열망 할 수있는 것 같습니다. :) 아마도 훌륭한 통찰력은 아니지만, 저에게는 이러한 "기술적"순간에 더 많은주의를 기울이는 것이 좋은 교훈이었습니다. 아이디어와 알고리즘을 실제 솔루션으로 변환합니다.
Swift 4 Solution 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
}
이것은 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에게 감사드립니다! 희소성을 활용하는 루비 구현이 있습니다.
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에서 위에 언급 된 아이디어 구현 :
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);
}
}
다음은 코드성에 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;
}
}
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;
}
여기에 라이브러리, 바이너리 검색, 정렬 등이 필요없는 2 패스 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)공간 복잡도.
주요 아이디어 :
- 2 개의 정렬 된 배열을 만듭니다 : 왼쪽 포인트와 오른쪽 포인트.
- 이러한 배열을 하나의 부울 배열로 병합합니다. 여기서는
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;
}
아래는 Kotlin에서 @Aryabhatta가 수락 한 답변을 구현 한 것이므로 모든 크레딧은 @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
}
100 % 점수를 가진 Codility Solution .
다음은 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
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;
참고URL : https://stackoverflow.com/questions/4801242/algorithm-to-calculate-number-of-intersecting-discs
반응형
'IT TIP' 카테고리의 다른 글
| Intellij 14 이상한 편집기 / 커서 동작 (0) | 2020.12.09 |
|---|---|
| 하위 폴더에서 루트 폴더의 이미지 선택 (0) | 2020.12.09 |
| cmd.exe (배치) 스크립트의 배열, 연결 목록 및 기타 데이터 구조 (0) | 2020.12.09 |
| ArrayList에서 요소의 모든 발생 제거 (0) | 2020.12.09 |
| 리소스가 글꼴로 해석되지만 MIME 유형 application / x-font-woff로 전송 됨 (0) | 2020.12.09 |