9

求人応募の一環として実際のテストを受ける前に、Codilityのデモ問題を試しています。彼らが持っているデモの1つは、ディスクのアレイのディスク交差の数を数えることを含む問題です。

タスクの説明は

N個の整数の配列Aが与えられた場合、I番目のディスクが（0、I）を中心とし、半径がA [I]になるように、2D平面にN個のディスクを描画します。J≠Kであり、J番目とK番目のディスクに少なくとも1つの共通点がある場合、J番目のディスクとK番目のディスクは交差すると言います。関数を記述します：class Solution {public int number_of_disc_intersections（int [] A）; 上で説明したようにN個のディスクを記述する配列Aが与えられると、交差するディスクのペアの数を返します。

ここでテストを表示できます。

やや明白なO（n ^ 2）時間計算量の解決策がありますが、目的はO（n * log（n））です。

私が提供したすべての例で機能するこれと、codility（[1、5、2、1、4、0]）によって与えられた単純なテストケースを思いついたが、Codilityはほとんどの場合失敗すると言っている他の人が、私は理由がよくわかりません。

n個のディスクのそれぞれをTreeSetに追加するのはlognであるため、これは確かにO（n log n）である必要があります。次に、O（1）操作TreeSet.headSet（）のみを使用して、各ディスクをウォークスルーします。

import java.util.*;

class Circle implements Comparable<Circle> {
  long edge;
  int index;

  Circle (long e, int i){
    edge = e;
    index = i;
  }

  long getRightAssumingEdgeIsLeft(){
    return (long)(2*index - edge + 1);
  }

  @Override
  public int compareTo(Circle other){
    return Long.valueOf(edge).compareTo(other.edge);
  }
}

class Solution {
  public int number_of_disc_intersections ( int[] A ) {
    int N = A.length;
    if (N<2) return 0;
    int result = 0;

    SortedSet<Circle> leftEdges  = new TreeSet<Circle>();
    for (int i=0; i<N; i++) {
      leftEdges.add( new Circle( (long)(i-A[i]), i ) );
    }
    int counter = 0;
    for (Circle c : leftEdges) {
      long rightEdge = c.getRightAssumingEdgeIsLeft();
      Circle dummyCircle = new Circle (rightEdge, -1);
      SortedSet<Circle> head = leftEdges.headSet(dummyCircle);
      result +=  head.size() - counter;
      if (result > 10000000) return -1;
      counter++;
    }
    return result;
  }
}
4

9 に答える 9

17

別のアルゴリズム ( O(N log N)):

シナリオのこの悪い図:

ここに画像の説明を入力

範囲のリストに変換できます: (まったく同じシナリオではありません)

図2 ここに画像の説明を入力

O(N log N): 最初にマーカーを並べ替えます。接線ディスクをオーバーラップとしてカウントする場合は、緑のマーカーが赤のマーカーの前に表示されるように注意します。

O(N): 左から右に、totalinitial= 0とoverlapsinitialでスキャンし= 0ます。緑色のマーカーにヒットするたびにtotal += 1、およびすべての赤色のマーカーにヒットするたびにtotal -= 1. さらに、各緑色のマーカーでは、if total > 0, then overlaps += total.

図2の黒い数字はtotal各ステップです。オレンジはoverlaps。

それならoverlaps答えがあるはずです。

ここで大まかな実装を参照してください: http://ideone.com/ggiRPA

于 2012-12-26T15:37:06.367 に答える
3

もっと簡単な方法があります...

  1. N 要素 (leftEdge、rightEdge) の 2 つの配列を作成します。
  2. 各要素について、左右の端 (インデックス -/+ 値) を計算し、配列に設定します。
  3. 配列をソートします。
  4. rightEdge 配列の各要素について、leftEdge 配列をループして、最初のより大きいか等しい要素を見つけます。残りの要素数と現在のインデックスを保存します。次の要素では、保存されたインデックスからループを開始します...

このようにして、並べ替えられた各配列を実際に 1 回だけループするため、アルゴリズムの複雑さは O(N log N) になります。

于 2013-03-30T00:27:19.790 に答える
2

このメソッドには、サークルなどの特別なクラスや、PriorityQueue や TreeSet などの複雑なコンテナーは必要ありません。必要なのは単純な整数配列だけです。O(N * logN) です。言語はJavaです。

public int numberOfDiscIntersections(int [] A) {
    // 0 <= A.length <= 100,000
    // 0 <= A[i] <= 2147483647
    int [] leftEdge = new int[A.length];
    int [] rightEdge = new int[A.length];

    int maxLength = 100000;
    // maxLength is used to prevent integers > 2147483647
    // and integers < -2147483647
    for (int i = 0; i < A.length; i++) {
        leftEdge[i] = i - A[i];
        rightEdge[i] = i - maxLength + A[i];
    }
    Arrays.sort(leftEdge);
    Arrays.sort(rightEdge);

    int sum = mergeAndCountOverlaps(leftEdge,rightEdge, maxLength);
    return sum;
}

マージ ルーチンは、マージ ソートからの変更されたマージです。2 つの並べ替えられた配列をマージし、並べ替え順序をそのまま維持し、オーバーラップ カウント機能を追加します。この場合、マージされた配列を返す必要はなく、オーバーラップ カウントのみを返します。

private int mergeAndCountOverlaps(int[] leftEdge, int [] rightEdge, int maxLength) {
    int leftIndex = 0;
    int rightIndex = 0;
    int sum = 0;
    int total = 0;
    while ((leftIndex < leftEdge.length) || (rightIndex < rightEdge.length)) {
        if ((leftIndex < leftEdge.length) && (rightIndex < rightEdge.length)) {
            boolean compareLeftEdgeandRightEdge;
            if (leftEdge[leftIndex] < -2147483647 + maxLength) {
                compareLeftEdgeandRightEdge = leftEdge[leftIndex] <= rightEdge[rightIndex] + maxLength;
            } else {
                compareLeftEdgeandRightEdge = leftEdge[leftIndex] - maxLength <= rightEdge[rightIndex];
            }
            if (compareLeftEdgeandRightEdge) {
                // a new left edge
                sum += total;
                if (sum > 10000000) {
                    return -1;
                }
                total++;
                leftIndex++;
            } else {
                // a new right edge
                total--;
                rightIndex++;
            }
        } else if (leftIndex < leftEdge.length) {
            // a new left edge
            sum += total;
            if (sum > 10000000) {
                return -1;
            }
            total++;
            leftIndex++;
        } else if (rightIndex < rightEdge.length) {
            // a new right edge
            total--;
            rightIndex++;
        }
    }
    return sum;
}
于 2014-07-04T05:08:54.747 に答える
1

まず、compareTo() を定義しましたが、equals() は定義しませんでした。TreeSet JavaDoc は次のように述べています。

edgeその他の奇妙な点:フィールドが何なのか、なぜ に設定したのかわかりませんi - A[i]。

于 2012-12-26T15:26:14.400 に答える
0

プログラミングのポジションに備えて、同じデモを行いました。私は時間内に解決策を開発することができず、結果としてひどいスコアを獲得しました (10 代の何か)。しかし、その質問に興味をそそられて、私は先に進み、自分でそれを完成させました. これが私の解決策です：

 ============================================================================
 Name        : cFundementalsTest.c
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(void) {

    int N = 5;
    int A[6] = {1, 5, 2, 1, 4, 0 };

        int pos_1, pos_2;
        int total;
        for(pos_1=0;pos_1<=N;pos_1++)
        {
            for(pos_2=pos_1+1;pos_2<=N;pos_2++)
            {
                if(A[pos_1] + A[pos_2] >= abs(pos_1 - pos_2))
                { // they share a common point
                    total++;
                    printf("%d and %d\n",pos_1, pos_2);
                    if(total > 10000000)
                        return(-1);
                }
            }
        }
        printf ("\n\n the total is %d",total);
}

そして、ここに正しいように見える結果があります:

0 and 1
0 and 2
0 and 4
1 and 2
1 and 3
1 and 4
1 and 5
2 and 3
2 and 4
3 and 4
4 and 5

 the total is 11
于 2013-06-09T19:02:12.950 に答える
-2

j が常に i よりも大きいと仮定すると、2 つの円が相互作用することを満たすために、以下の不等式が常に機能するはずです。

|R(i) - R(j)| <= j - i <= R(i) + R(j)

それは別の言い方です：

abs(A[i] - A[j]) <= j - i <= A[i] + A[j]

私はテストしていませんが、うまくいくと思います。それが役に立てば幸い。

#include <stdlib.h>

public int number_of_disc_intersections(int[] A){

    int len = A.length;
    int intersections = 0;

    for(int i = 0; i < len - 1; i++){

        if(A[i] <= 0){
            continue;
        }

        for(int j = i + 1; j < len; j++){

            if(A[j] <= 0){
                continue;       
            }

            if(abs((A[i] - A[j]) <= j - i) && (j - i <= A[i] + A[j])){
                intersections ++;
            }
        }
    }

    return intersections;
}
于 2013-04-24T16:19:08.790 に答える