【面试新题】绝妙的二分查找题，一定要练习一下

C++ version

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

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

补充内容 (2019-5-18 06:24):
输出
3
5
6
7
8
12
13
14
-1
-1
-1
-1
-1
-1
-1
-1

1.     def findKthMissing(self, nums, k):
   
2.         def helper(nums, left, right, k):
   
3.             if left == right: return nums[left] + k
   
4.             mid = (left + right) // 2
   
5.             if (nums[left] + mid - left + k) < nums[mid + 1]:
   
6.                 return helper(nums, left, mid, k)
   
7.             else:
   
8.                 return helper(nums, mid+1, right, k - (nums[mid+1] - nums[left] - (mid-left)) + 1)
   
9.         return helper(nums, 0, len(nums)-1, k)

复制代码

Java version, 送一个unittest

1. import static org.junit.Assert.*;
   
2. 
   
3. import org.junit.Test;
   
4. 
   
5. public class KthMissingNumber {
   
6.        
   
7.         public int solution(int[] arr, int k) {
   
8.                 int left = 0, right = arr.length - 1;
   
9.                 while (left + 1 < right) {
   
10.                         int mid = left + (right - left) / 2;
    
11.                         int missingNum = arr[mid] - arr[left] - (mid - left);
    
12.                         if (missingNum >= k) {
    
13.                                 right = mid;
    
14.                         } else if (missingNum < k) {
    
15.                                 k = k - missingNum;
    
16.                                 left = mid;
    
17.                         }
    
18.                 }
    
19.                 return arr[left] + k >= arr[right] ? -1 : arr[left] + k;
    
20.         }
    
21.        
    
22.         @Test
    
23.         public void test() {
    
24.                 KthMissingNumber kmn = new KthMissingNumber();
    
25.                 int[] testArr = new int[] {2, 4, 7, 8, 9, 15};
    
26.                 int[] expection = new int[] {3, 5, 6, 10, 11, 12, 13, 14, -1, -1};
    
27.                 for (int i = 0; i < 10; i++) {
    
28.                         assertEquals(kmn.solution(testArr, i + 1), expection[i]);
    
29.                 }
    
30.         }
    
31. 
    
32. }
    

复制代码

补充内容 (2019-5-20 17:48):
有点typo 大家无视

贴一个 JavaScript 版解法
不是很 robust，但足够作为面试答案

1. const kthMissingNumber = (arr, k) => {
   
2. 
   
3.     let left = 0, right = arr.length - 1
   
4. 
   
5.     while (left + 1 < right) {
   
6.         let mid = Math.floor((left + right) / 2)
   
7.         // calculate the number of missing numbers
   
8.         nMissed = (arr[mid] - arr[left]) - (mid - left)
   
9.         if (nMissed < k) {
   
10.             left = mid
    
11.             k = k - nMissed
    
12.         } else {
    
13.             right = mid
    
14.         }
    
15.     }
    
16. 
    
17.     if (arr[left] + k >= arr[right]) return -1
    
18.     return arr[left] + k
    
19.    
    
20. }
    

复制代码

唉，看不了啊...靠每日登陆和答题一个月了，还是好多好多看不了。哪位大哥哥大姐姐赏点分

感谢分享，非常好的一道题

这道题确实蛮有意思的

两个月不刷题，看到这题都没有什么思路。。感谢分享！

liaohs49 发表于 2019-5-18 20:38
Java version, 送一个unittest
[mw_shl_code=java,true]import static org.junit.Assert.*;

You are given a sorted without any duplicate integer array

test case 要改改

补充内容 (2019-5-20 01:42):
my fault, never mind

挺好的写的