配列内のn個の異なる2次元点をカウントするためのアルゴリズムを設計するには

debugcn 投稿 Dev

サロニアグラワル

public class IntersectionOfTwoSets {

public class Point implements Comparable{
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Object o) {
        if(this.x > ((Point)o).x) return 1;
        if(this.x < ((Point)o).x) return -1;
        if(this.y > ((Point)o).y) return 1;
        if(this.y < ((Point)o).y) return -1;
        return 0;
    }
}

public Point[] intersectionOf(Point[] a, Point[] b) {
    List<Point> result = new ArrayList<>();
    Arrays.sort(a);
    Arrays.sort(b);

    for(int i = 0, j = 0; i < a.length && j < b.length; ) {
        if(a[i].compareTo(b[j]) == 0) {
            result.add(a[i]);
            i++;
            j++;
        } else if (a[i].compareTo(b[j]) < 0) {
            i ++;
        } else {
            j ++;
        }
    }
    return (Point[])result.toArray();
}

n個の異なる2Dポイントを含む2つの配列aとbが与えられます。両方の配列に含まれるポイントの数をカウントするアルゴリズムを設計します（コードの理解の問題）このコードに関連する複数の質問があります。

ネストされたクラスを作成するのはなぜですか？
ステートメントのためにiとjをインクリメントするのではなく、bodyの場合にelseでiとjをインクリメントするのはなぜですか？
mainメソッドはどのように2点配列のオブジェクトを作成しますか？

（誰かがこの質問に対するより良い解決策を持っているなら、それは本当にありがたいです。）

g6r6u

私はC ++を使用していますが、あなたの質問に答えることができます。アルゴリズムは大丈夫です~~ただし、アルゴリズムを理解するのに問題があることを反映するように質問を言い換える必要があります~~。

1）ネストされたクラスを作成するのはなぜですか？
タイプの競合を回避するには

+- IntersectionOfTwoSets (class) ------+
|    |                                 |
|    o- Point (class)                  |
|    |                                 |
|    o- intersectionOf (function)      |
|                                      |
+--------------------------------------+

なしで実装できますが、これは非常に一般的な名前であり、プロジェクトに追加する予定のライブラリにすでに実装されている可能性IntersectionOfTwoSetsがあることに注意しPointてください。で実装PointするIntersectionOfTwoSetsと、実装が一意になります（namespaceC ++で知られている概念であり、その使用は優れたプログラミング手法と見なされます）

標準ループのための構文は次のとおりですfor（init; condition; increment）

ループ内で見つける代わりに、ループの増分コンポーネントが欠落していることを確認してください

2）i ++とj ++はintersectionOfメソッドにどのように実装されていますか？
i++単にi += 1;

これがコードの簡略版です

given two sets a & b
sort a & b
initialize empty array (result)
loop (...)
| if (a[i] == b[j])
|  add a[i] to result, then increment i & j
| if (a[i] < b[j])
|  increment i
| if (b[j] < a[i])
|  increment j
| if (i >= a.size()) or (j >= b.size())
|  stop
return result

整数のセットでアルゴリズムをテストしてみましょう

let a: [2, 1, 10, 9]
let b: [1, 5, 2, 7, 6]

let result: []

Arrays.sort(a); // a: [1, 2, 9, 10]
Arrays.sort(b); // b: [1, 2, 5, 6, 7]

loop(...)
| 1: add 1 to result, increment i & j
| 2: add 2 to result, increment i & j
| 3: (j == 2) increment only j (5 < 9)
| 4: (j == 3) increment only j (6 < 9)
| 5: (j == 4) increment only j (7 < 9)
| 6: (j == 5) stop because j >= b.size()

return result // [1, 2]

一連のポイントでも機能するはずです

3）mainメソッドはどのように2点配列のオブジェクトを作成しますか？
C ++では、構文は次のとおりです。

IntersectionOfTwoSets::Point a[n], b[n];
or
List<IntersectionOfTwoSets::Point> a, b;

しかし、Javaでは、ほぼ確実に次のようになります。

List<IntersectionOfTwoSets.Point> a, b;
or
IntersectionOfTwoSets::Point a = new IntersectionOfTwoSets::Point[n];
IntersectionOfTwoSets::Point b = new IntersectionOfTwoSets::Point[n];

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]