非死不可 根本不想给过电面

这个题可以用heap吧？跟第k大/小不是一样的题吗？

替楼主惋惜。祝拿到大offer。
我也是follow楼主的思路，写了以下的代码供大家参

1.     public int kth(int n, int k) {
   
2.         k += 1;
   
3.         int numOfBitOne = 0;
   
4.         while (numOfBitOne <= n) {
   
5.             int cnt = nCr(n, numOfBitOne);
   
6.             if (k <= cnt) break;
   
7.             k -= cnt;
   
8.             ++numOfBitOne;
   
9.         }
   
10.         int num = 0;
    
11.         while (n > 0) {
    
12.             // Number of corresponding numbers which have numberOfBitOne 1s when most significant bit is set to 0
    
13.             int msb0 = (n - 1 >= numOfBitOne) ? nCr(n - 1, numOfBitOne) : 0;
    
14.             if (k <= msb0)
    
15.                 num = num * 2;
    
16.             else {
    
17.                 k -= msb0;
    
18.                 num = num * 2 + 1;
    
19.                 --numOfBitOne;
    
20.             }
    
21.             --n;
    
22.         }
    
23.         return num;
    
24.     }
    
25. 
    
26.     private int nCr(int n, int r) {
    
27.         return factorial(n) / factorial(r) / factorial(n - r);
    
28.     }
    
29.    
    
30.     // We can use a HashMap to store the n -> n! to avoid duplicate calculations.
    
31.     private int factorial(int n) {
    
32.         if (n == 0 || n == 1) return 1;
    
33.         return n * factorial(n - 1);
    
34.     }

复制代码

Test code:

1.     public static void main(String[] args) {
   
2.         KthNumberOf1s o = new KthNumberOf1s();
   
3.         System.out.println(o.kth(3, 4) == 3);
   
4.         System.out.println(o.kth(4, 5) == 3);
   
5.         System.out.println(o.kth(4, 6) == 5);
   
6.         System.out.println(o.kth(4, 7) == 6);
   
7.         System.out.println(o.kth(4, 8) == 9);
   
8.     }

复制代码

哈哈楼主我也是这样的，遇到的三哥都是过程问啥啥不说，然后aggresive 挑毛病。昂赛遇到三哥也是必hard或没见过的难题。国人都是死命帮你

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

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