- 1. 题目
- 2. 思路
- (1) 贪心算法
- 3. 代码
- 贪心策略是优先安排小个子,根据小个子属性中的k值,为其前面留够k个空位即可,因为后面被安排的人必然比其要高。
- 需要对原来的数组进行排序,小个子在前,高个子在后,若两个人的身高相等,则按照k值从大到小进行排序,因为k值中包含了相等身高的人。
import java.util.Arrays; import java.util.Comparator; public class Test { public static void main(String[] args) { } } class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]; } }); int n = people.length; int[][] res = new int[n][]; for (int[] person : people) { int space = person[1]; for (int i = 0; i < n; i++) { if (res[i] == null) { if (space > 0) { space--; } else { res[i] = person; break; } } } } return res; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)