在一排座位中饰恕，找到與兩邊人距離的最遠的位置
class Solution {
public int findSeat(int[] people) {
if (people == null || people.length == 0) {
return -1;
}
int idx = -1;
int maxLen = Integer.MIN_VALUE;
int cnt = 0;
for (int i = 0; i < people.length; i++) {
if (people[i] == 0) {
cnt++;
} else {
if (cnt > maxLen) {
maxLen = cnt;
idx = i - cnt;
}
cnt = 0;
}
}
if (idx == -1) {
return -1;
}
return idx + maxLen / 2;
}
}
Follow-up:
凳子上一開始沒有人丈冬，然后一個一個往里面放吠勘，每次放的時候O(1)時間求放在哪里距離最大（數(shù)學(xué)問題 )
search O(1)
Use priority queue (maxHeap)
class Solution {
public int[] findSeat(int numOfPeople, int seats) {
if (seats == 0) {
return -1;
}
Comparator<int[]> comp = new ComparatorMax();
PriorityQueue<int[]> q = new PriorityQueue<>(2 * seats, comp);
int[] rst = new int[seats];
q.offer(new int[] {0, seats});
for (int i = 0; i < numOfPeople; i++) {
int[] l = q.poll();
int idx = l[0] + l[1] / 2;
rst[idx] = i;
q.offer(new int[] {l[0], l[1] / 2});
q.offer(new int[] {idx + 1, l[1] - l[1]/ 2 - 1});
}
}
return rst;
}
class ComparatorMax implements Comparator<Integer> {
@Override
public int compare(int[] a, int[] b) {
if (a[1] > b[1]) {
return -1;
}
if (a[1] < b[1]) {
return 1;
}
if (a[0] < b[0]) {
return -1;
} else if (a[0] > b[0]) {
return 1;
}
return 0;
}
}
