【学習ノート】leetcode 1203
3913 ワード
public class Solution {
int groupNumx = 0;
int[] itemIndegree = null;
int[] groupIndegree = null;
Item[] items = null;
Group[] groups = null;
public int[] sortItems(int n, int m, int[] group, List> beforeItems) {
if (n == 0 || group == null || group.length == 0 || beforeItems == null || beforeItems.size() == 0) {
return new int[0];
}
init(n, m, group, beforeItems);
Integer[] groupIdx = new Integer[groupNumx];
for (int i = 0; i < groupNumx; i++) {
groupIdx[i] = i;
}
List groupG = sort(groupIdx, groups, groupIndegree);
if (groupG == null) {
return new int[0];
}
int[] ret = new int[n];
int idx = 0;
for (int g : groupG) {
List itemG = sort(groups[g].items.toArray(new Integer[0]), items, itemIndegree);
if (itemG == null) {
return new int[0];
}
for (int item : itemG) {
ret[idx++] = item;
}
}
return ret;
}
private void init(int n, int m, int[] group, List> beforeItems) {
groupNumx = 0;
int g = 0;
for (int i = 0; i < n; i++) {
if (group[i] == -1) {
group[i] = m + g++;
}
}
groupNumx = g + m;
groupIndegree = new int[groupNumx];
groups = new Group[groupNumx];
for (int i = 0; i < groupNumx; i++) {
groups[i] = new Group(i);
}
items = new Item[n];
itemIndegree = new int[n];
for (int i = 0; i < n; i++) {
items[i] = new Item(i);
groups[group[i]].items.add(i); //
}
for (int i = 0; i < beforeItems.size(); i++) {
// i item id
// list item i
List list = beforeItems.get(i);
// j
for (int j : list.toArray(new Integer[0])) {
if (group[i] == group[j]) { // , ,
itemIndegree[i]++;
items[j].adjecent.add(i);
groups[group[j]].items.add(i);
groups[group[j]].items.add(j);
} else { //
groups[group[j]].adjecent.add(group[i]);
}
}
}
//
for (int j = 0; j < groups.length; j++) {
// j
// k
for (int k : groups[j].adjecent.toArray(new Integer[0])) {
groupIndegree[k]++;
}
}
}
private List sort(Integer[] ids, Item[] items, int[] degrees) {
List ret = new LinkedList<>();
Deque deque = new LinkedList<>();
for (int id : ids) {
if (degrees[id] == 0) {
deque.add(id);
}
}
while (!deque.isEmpty()) {
int id = deque.poll();
ret.add(id);
Integer[] adjecents = items[id].adjecent.toArray(new Integer[0]);
for (int adjecent : adjecents) {
if (--degrees[adjecent] == 0) {
deque.addFirst(adjecent); // ,
}
}
}
if (ret.size() != ids.length) {
return null;
}
return ret;
}
}
class Item {
int id;
Set adjecent;
public Item(int id) {
this.id = id;
adjecent = new HashSet<>();
}
}
class Group extends Item{
Set items;
public Group(int id) {
super(id);
items = new HashSet<>();
}
}