Dados n puntos en un plano 2D, encuentre si existe una línea paralela al eje y que refleje los puntos dados.
Ejemplo 1:
Puntos dados = [[1,1],[-1,1]]devuelve verdadero.
Ejemplo 2:
Puntos dados = [[1,1],[-1,-1]], falso retorno.
Hacer un seguimiento:
¿Podrías hacerlo mejor que O (n2)?
Solución Java
Para este problema, primero encontramos el valor x más pequeño y más grande para todos los puntos y obtenemos que el eje x de la línea es (minX + maxX) / 2, luego, para cada punto, verificamos si cada punto tiene puntos de reflexión en el conjunto.
public boolean isReflected(int[][] points) { if(points==null || points.length<2) return true; HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>(); int min=Integer.MAX_VALUE; int max=Integer.MIN_VALUE; for(int[] arr: points){ min = Math.min(min, arr[0]); max = Math.max(max, arr[0]); HashSet<Integer> set = map.get(arr[0]); if(set==null){ set = new HashSet<Integer>(); map.put(arr[0], set); } set.add(arr[1]); } int y = min+max; for(int[] arr: points){ int left = arr[0]; int right = y-left; if(map.get(right)==null || !map.get(right).contains(arr[1])){ return false; } } return true; } |
