脸书电面

发个前一阵脸书电面攒攒人品，面试官只准备了一道题。
给一个长度为N的array， 然后里面有M个部分， 每一部分都是排好序的，输出排好

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ong>
其实就是个变种的merge k sorted array， 用heap就可以

用一个list把每个sort segment的start point 和endpoint记起来，然后按Merge K List 来做。
space：O（K）k是sort segment

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问是类似于merge k sorted arrya的做法么  一开始先遍历一遍数组  然后把数组分割成一个个sorted的子数组？

请问一下，OA 编程语言可以选Ruby吗?  

请问有要求space complexity么？有要求是O(K)么？如果这样子的话，请问如何在不改动原数组的情况下进行merge&sort呢？

同问是不是merge k sorted array方法？

1. class ArrayContainer implements Comparable<ArrayContainer> {
   
2.     int num;
   
3.     int idx;
   
4.     public ArrayContainer(int num, int idx) {
   
5.         this.num = num;
   
6.         this.idx = idx;
   
7.     }
   
8. 
   
9.     @Override
   
10.     public int compareTo(ArrayContainer a) {
    
11.         return this.num - a.num;
    
12.     }
    
13. }
    
14. public class SortArray {
    
15. 
    
16.     private int[] solution(int[] nums, int m, int n) {
    
17.         int bucketSize = n / m;
    
18.         int[] res = new int[n];
    
19.         int j = 0;
    
20.         PriorityQueue<ArrayContainer> pq = new PriorityQueue<ArrayContainer>();
    
21.         for (int i = 0; i < nums.length; i += bucketSize) {
    
22.             pq.add(new ArrayContainer(nums[i], i));
    
23.         }
    
24.         while (!pq.isEmpty()) {
    
25.             ArrayContainer arr = pq.poll();
    
26.             int num = arr.num;
    
27.             res[j] = num;
    
28.             j++;
    
29.             int idx = arr.idx;
    
30.             if ((idx + 1) % bucketSize != 0) {
    
31.                 pq.add(new ArrayContainer(nums[idx + 1], idx + 1));
    
32.             }
    
33.         }
    
34. 
    
35.         return res;
    
36.     }
    
37. 
    
38.     public static void main(String[] args) {
    
39.         SortArray sortArray = new SortArray();
    
40.         int[] res = sortArray.solution(new int[]{2,5,6, 1,2,4, 9, 11, 12}, 3, 9);
    
41.         System.out.println(Arrays.toString(res));
    
42.     }

复制代码

请问 1,2,4, 9, 11, 12 ，算一个部分，还是2个部分， 1，2，4 然后，9，11，12？

oumizx 发表于 2020-4-21 18:01
[mw_shl_code=bash,true]class ArrayContainer implements Comparable {
    int num;
    int idx;

貌似没有说M是等分的噢? 应该需要手动找一下了可能