Two Furthest Houses With Different Colors
给一个数组, 求两个不同数字的最大距离.
这题讨论里的人O(N^2)都100%, 我O(N*100)居然8%…
就是利用map的put的原理(重复覆盖相同元素). 然后再扫一次即可.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public int maxDistance(int[] colors) { Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < colors.length; i++) { map.put(colors[i], i); } int res = 0; for(int i = 0; i < colors.length; i++) { for(int j = 0; j <= 100; j++) { if(j != colors[i]){ res = Math.max(res, map.getOrDefault(j, i) - i); } } } return res; } } |