根据身高重建队列力扣--406

打印 上一主题 下一主题

主题 1013|帖子 1013|积分 3039

目录

标题
思绪
代码


标题

假设有打乱次序的一群人站成一个队列,数组 people 表现队列中一些人的属性(不一定按次序)。每个 people = [hi, ki] 表现第 i 个人的身高为 hi ,前面 恰恰 有 ki 个身高大于或即是 hi 的人。
请你重新构造并返回输入数组 people 所表现的队列。返回的队列应该格式化为数组 queue ,此中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。

  示例 1:
  1. <strong>输入:</strong>people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
  2. <strong>输出:</strong>[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
  3. <strong>解释:</strong>
  4. 编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。
  5. 编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。
  6. 编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。
  7. 编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
  8. 编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。
  9. 编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
  10. 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
复制代码
示例 2:
  1. <strong>输入:</strong>people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
  2. <strong>输出:</strong>[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
复制代码
思绪

本题有两个维度,h和k,看到这种标题一定要想怎样确定一个维度,然后再按照另一个维度重新排列。
先按照h排序还是k排序呢?
按照k排序 ,排完之后,会发现k的排列并不符合条件,身高也不符合条件,两个维度哪一个都没确定下来。
以是按照身高排序,从大到小排序

插入的过程:


  • 插入[7,0]:[[7,0]]
  • 插入[7,1]:[[7,0],[7,1]]
  • 插入[6,1]:[[7,0],[6,1],[7,1]]
  • 插入[5,0]:[[5,0],[7,0],[6,1],[7,1]]
  • 插入[5,2]:[[5,0],[7,0],[5,2],[6,1],[7,1]]
  • 插入[4,4]:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
 当他把【6,1】插入到【7,1】前面的话,不会影响【7,1】前面只有一个大于即是他的情况,以是说从大到小排序
代码

  1. class Solution {
  2.     public int[][] reconstructQueue(int[][] people) {
  3.         Arrays.sort(people,(a,b)->{
  4.             if(a[0]==b[0]) return a[1]-b[1];
  5.             return b[0] - a[0];});
  6.         
  7.         LinkedList<int []>que=new LinkedList<>();
  8.         for (int[] p : people) {
  9.             que.add(p[1],p);   //Linkedlist.add(index, value),会將value插入到指定index里。
  10.         }
  11.         
  12.          return que.toArray(new int[people.length][]);
  13.     }
  14. }
复制代码
匿名 Comparator 实现
  1. (a, b) -> {
  2.     if (a[0] == b[0]) return a[1] - b[1];
  3.     return b[0] - a[0];
  4. }
复制代码
这是一个 Lambda 表达式,用于实现 Comparator 接口。a 和 b 是 people 数组中的两个元素,每个元素都是一个长度为 2 的一维数组,分别代表一个人的身高 h 和前面身高大于即是本身的人数 k。



  • if (a[0] == b[0]) return a[1] - b[1];

    • 这行代码的作用是当两个人的身高 h 相等时,按照 k 值进行升序排序。
    • a[1] - b[1] 的效果决定了 a 和 b 的相对次序:

      • 如果 a[1] - b[1] < 0,分析 a[1] 小于 b[1],a 会排在 b 前面。
      • 如果 a[1] - b[1] > 0,分析 a[1] 大于 b[1],a 会排在 b 后面。
      • 如果 a[1] - b[1] == 0,分析 a[1] 即是 b[1],a 和 b 的相对次序不变。


  • return b[0] - a[0];

    • 这行代码的作用是当两个人的身高 h 不相等时,按照 h 值进行降序排序。
    • b[0] - a[0] 的效果决定了 a 和 b 的相对次序:

      • 如果 b[0] - a[0] < 0,分析 b[0] 小于 a[0],b 会排在 a 后面。
      • 如果 b[0] - a[0] > 0,分析 b[0] 大于 a[0],b 会排在 a 前面。
      • 如果 b[0] - a[0] == 0,这种情况不会出现,由于前面已经处置惩罚了 a[0] == b[0] 的情况。


 


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

西河刘卡车医

论坛元老
这个人很懒什么都没写!
快速回复 返回顶部 返回列表