入力は、円周上に位置する点は をペアリングして接続されている方法と言って線分を定義する2n個の整数の配列です。 (各点は、それに接続し、独自の対を有する。)エンドポイントが円上にある線分の交差数を数えますか?
アレイ
[2,3,0,1]
読み取り:ポイント0は2
ポイント1点に接続されている点に接続されている3
ポイント2は0
を指すように接続されています。ポイント3は ポイント1に接続されます意味私たちは線分(0,2)と(1,3)を持っています。
点は、配列内にある と同じ順序で円に配置されています。 (正確な座標は無関係です)
ここに私の配列の例があります。 (1つの交差点が発生しました。)
出力は交差点の数です。 (2つの線分が接触する点の数)
これを計算するにはどのような方法が最善でしょうか?
public static int countIntersections(int[] world) { int intersections = 0; for (int i = 1; i < world.length; i++) { for (int j = 0; j < i; j++) { if (!C(i,world[i],i-j,world[i-j])) { intersections++; } } } return intersections; } public static boolean C(int a, int b, int x, int y) { return ((a <= x && b <= x) || (a >= x && b <= y) || (a >= x && b >= x)); }
彼らに仕事の両方を意味する私の最初のコードと同じ結果を与える:sabyの答えに
public static int count(int[] world) { int i = 0; int intersections = 0; int endpoint = 0; // run trought all points in order, find their pairs and check if the line they make is intersected while (i < world.length - 1) { if (world[i] == i+1) { // if 2 neighbouring points are connected, there are no intersections with the line they make i++; } else if (world[i] > i) { // don't need to check previously checked pairs endpoint = world[i]; // check if any intersections with the line L(i,world[i]): // This goes through all points that are located before the endpoint of the line defined by point i and its pair world[i] // And checks if their pair is located after the endpoint, which means that the line they make intersects the line L(i,world[i]) for (int j = i+1; j < endpoint; j++) { if (world[j] > endpoint) { intersections++; } } } i++; } return intersections; }
おかげで、私はまた、これをコード化:私が試した何
!しかし私の初期のコードはこれより高速です。
両方のコードが動作し、最適化の質問がCodereviewに適しているので、私は彼の答えを受け入れます。
なぜdownvoteですか? – saby
+1、後で試してみます。私は誰かが通り過ぎていて、質問とこの答えの両方を理由なしでdownvotedしたと思います... – Vepir
どのくらい奇妙です!はい、試して、フィードバックをしてください。あなたが時間の複雑さを改善したいなら、それができるかもしれません。 – saby