Found_HashMap_DistinctPoints

Question

 Given N 2D Points, Calculate no. of distinct points among them.

 Ex: x[5] = {2, 1, 3, 2, 2}
 y[5] = {3, 1, 2, 3, 4}

 The first array represents the x co-ordinates, the second array represents the y co-ordinate.       Acoording to above examples the points are 
(x[0],y[0])->(2,3)
(x[1],y[1])->(1,1)
(x[2],y[2])->(3,2)
(x[3],y[3])->(2,3)
(x[4],y[4])->(2,4)

Total number of distinct points are 4.

我通过创建两个 HashMap 并将索引存储为键，将元素存储为值来编写上述问题的实现。但是，代码给出了错误的输出：对于上述测试用例，我的代码的输出是“5”而不是“4”。实现如下：

      HashMap<Integer,Integer> mpp1 = new HashMap<>();
        HashMap<Integer,Integer> mpp2 = new HashMap<>();
        for(int i =0;i<n;i++){
            mpp1.put(i,x[i]);
        }
        for(int i =0;i<n;i++){
            mpp2.put(i,y[i]);
        }
        int count=0;
        boolean b=true;
        for(int i=0;i<n;i++){
            if(mpp1.get(i).equals(mpp2.get(i))==false){
                    b=false;
                   count++;
            }
          //  System.out.print(mpp1.get(i)+" ");
        }
       // if(b==true){
        //System.out.print("-1");
        //}
        
        System.out.print(count);

Answer 1

您的实现为我提供了上述问题的答案 4。

    int n=5;
    int[] x = new int[] {2, 1, 3, 2, 2};
    int[] y = new int[] {3, 1, 2, 3, 4};

所以它有效，因为它给出了预期的答案。但我认为这是错误的方法，因为您正在比较一个点的 x, y 坐标，其中 x=1, y=1 是唯一将 x 与 y 匹配的点，因此不被计算在内，这会导致 4 .

但是您正在寻找不同的 2D 点，2D 点是由 x、y 坐标定义的。所以point-0是x[0]和y[0]，point-1是x[1]和y[1]等等。 因此，按照这个方法，您需要首先找到您的点，然后比较它们各自的坐标。

（未优化）一种方法是首先找到匹配的 x 坐标，然后检查 y 是否也匹配，如果匹配，那么这是您的无明显点。 所以在你的例子中它将是点 0 (x=2, y=3) 和点 3 (x=2, y=3)。

代码可能如下所示：

    int[] x = new int[] {2, 1, 3, 2, 2};
    int[] y = new int[] {3, 1, 2, 3, 4};
    int noneUnique = 0;

    for(int i = x.length - 1; i > 0; i--) {
        for(int j = i - 1; j > -1; j--) {
            if (x[i] == x[j] && y[i] == y[j]) {
                noneUnique++;
            }
        }
    }

    System.out.format("found %d distinct points", x.length - noneUnique);