Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.
Example 1:
Given points = [[1,1],[-1,1]], return true.
Example 2:
Given points = [[1,1],[-1,-1]], return false.
Follow up:
Could you do better than O(n2)?
Solution1：selfencode + Hashset
思路： first pass先求出中心線并將每個(gè)點(diǎn)存入hashset澜掩，second pass 看是否每個(gè)點(diǎn)在中心線的對面對應(yīng)位置存在另一個(gè)點(diǎn)。
關(guān)于點(diǎn)存入hashset的方式：這里自己編碼了丙唧。因?yàn)閔ashset的key必須是id型既鞠，不能直接存collection蔽豺，但collection object可以通過hashCode轉(zhuǎn)成id存入蚪战，如solution2.
Time Complexity: O(N) Space Complexity: O(N)
Solution2：list_hashcode + Hashset
思路： 思路同1，但實(shí)現(xiàn)上直接將collection 通過 hashCode轉(zhuǎn)成id存入hashset
Solution1 Code：
class Solution {
public boolean isReflected(int[][] points) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
HashSet<String> set = new HashSet<>();
for(int[] p: points){
max = Math.max(max, p[0]);
min = Math.min(min, p[0]);
String str = p[0] + "a" + p[1];
set.add(str);
}
int sum = max + min;
for(int[] p: points){
String str = (sum - p[0]) + "a" + p[1];
if( !set.contains(str)) {
return false;
}
}
return true;
}
}
Solution2 Code：
class Solution2 {
public boolean isReflected(int[][] points) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
HashSet<Integer> set = new HashSet<>();
for(int[] p: points){
max = Math.max(max, p[0]);
min = Math.min(min, p[0]);
set.add(Arrays.hashCode(p));
}
int sum = max + min;
for(int[] p: points){
String str = (sum - p[0]) + "a" + p[1];
if(!set.contains(Arrays.hashCode(new int[]{sum - p[0], p[1]}))) {
return false;
}
}
return true;
}
}
