find duplicates in matrix within k indices

时间:2021-05-07 22:04:20
import java.util.*;
public class find_dupicates_within_k_indices {
    static class Pos {
        int row;
        int col;
        Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }
        public int getRow() {
            return row;
        }
        public int getCol() {
            return col;
        }
        public boolean equals(Object o) {
            Pos p = (Pos) o;
            if (p == null) return false;
            return p.row == row && p.col == col;
        }
        public int hashCode() {
            return this.row + this.col;
        }
    }
    public static void findDupicates(int[][] matrix, int k) {
        Map < Integer, Set < Pos >> store = new HashMap < Integer, Set < Pos >> ();
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                int val = matrix[row][col];
                if (store.containsKey(val)) {
                    Set < Pos > set = store.get(val);
                    for (Pos p: set) {
                        if (Math.abs(p.getRow() - row) + Math.abs(p.getCol() - col) <= k) {
                            System.out.println("YES");
                            return;
                        }
                        if (row - p.getRow() > k) set.remove(p);
                    }
                    set.add(new Pos(row, col));
                } else {
                    Set < Pos > set = new HashSet < Pos > ();
                    set.add(new Pos(row, col));
                    store.put(val, set);
                }
            }
        }
        System.out.println("NO");
        return;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        // int[][] matrix1 = {{1,2,3}, {4, 5, 6}, {7,8,9}, {10, 11, 12}};
        // int[][] matrix2 = {{1,2,3}, {3, 5, 6}, {7,8,9}, {10, 11, 12}};
        //
        // int k = 3;
        // findDupicates(matrix1, k);
        // findDupicates(matrix2, k);
        Scanner in = new Scanner(System. in );
        String tmp1;
        String tmp2;
        tmp1 = in .nextLine();
        tmp2 = in .nextLine();
        int row = Integer.parseInt(tmp1);
        String[] tmpNum = tmp2.split(" ");
        int col = tmpNum.length;
        int[] row1 = new int[col];
        for (int i = 0; i < col; i++) {
            row1[i] = Integer.parseInt(tmpNum[i]);
        }
        int[][] matrix = new int[row][col];
        matrix[0] = row1;

        for (int i = 1; i < row; i++) {
            String[] tmpStr = in .nextLine().split(" ");
            for (int j = 0; j < col; j++) {
                matrix[i][j] = Integer.parseInt(tmpStr[j]);
            }
        }
        int k = in .nextInt();
        // if(in.hasNextInt()) {
        // System.out.println("ERROR");
        // return;
        // }
        findDupicates(matrix, k);
    }
}