Maximize Distance to Closest Person
给一个数组, 找其中的0到两边1最短距离. 这个题N^2还是很好做的, 就是一个扫一边内嵌一个while双指针.
但是N的做法就需要点考虑, 我是用counting的方法, 遇到0就记录一下0的个数, 遇到1就知道前边0的个数, 这样除一下2就知道中间的位置.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public int maxDistToClosest(int[] seats) { int res = 0; int cur = 0; for (int i=0;i<seats.length;i++){ if (seats[i]==0){ cur++; // count the number of 0 } else { if (i-cur>0){ cur=cur/2 + cur%2; } res = Math.max(res,cur); cur=0; } } res = Math.max(res,cur); return res; } } |