谷歌NG VO新鲜面经

第二题 试了一些test case感觉是对的， 不知道有没有没cover的 欢迎讨论

1. public class Main {
   
2.   static public int peakIndexInMountainArray(int[] nums) {
   
3.     int left = 0;
   
4.     int right = nums.length - 1;
   
5. 
   
6.     while (left < right) {
   
7.       int mid = (left + right) / 2;
   
8.       while(right + 1 < nums.length -1 && nums[mid] == nums[right]){ // find the next valid right to know relation with mid
   
9.         right++;
   
10.       }
    
11.       if(nums[mid] <= nums[right]){ // if nums[mid] == nums[right] == nums[nums.length - 1], discard right side of mid
    
12.         right = mid;
    
13.       } else { // nums[mid] > nums[right], discard mid's left and mid
    
14.         left = mid + 1;
    
15.       }
    
16. 
    
17.     }
    
18.     return nums[left];
    
19.   }
    
20. 
    
21.   public static void main(String[] args){
    
22.                         //0 1 2 3 4 5 6 7 8 9 10 11  
    
23.     int[] arr = new int[]{5,4,4,3,2,2,1,1,2,2,2,3};
    
24.     // int[] arr = new int[]{2,2,2,1,2};
    
25.     int i = peakIndexInMountainArray(arr);
    
26.     System.out.println("min value index " + i);
    
27.   }  
    
28. }
    

复制代码

第二题是衣领九五的简单版，衣领九五是要求找到任意数字，且数字不会重复。

merge sort的套路，partition返回最小值，这样O(n log n)
binary search直接做不太好做，因为你没法判断左右相同的是左边的下坡还是右边的下坡，不管是去重还是单步前进找到下一个重复的都是O(n)
merge sort进阶版本的话，可以在看到left > mid或者mid < right就丢弃这一节，否则还是要持续遍历。

这里给一个刁钻的case: [9,9,9,9,9,1,9,9,9,9,9,9,9,9,9,9,9,9,9]

匿名用户 发表于 2023-10-18 01:16
第二题是衣领九五的简单版，衣领九五是要求找到任意数字，且数字不会重复。

merge sort的套路，partitio ...

不对 第二题是可以重复的, 而且关键就是去重 所以是衣领九五的升级版

感觉第一题是不是hashmap找item索引+priorityqueue负责排序

匿名用户 发表于 2022-10-25 09:11
感觉那题是反过来的，原理类似

有重复怎么处理呢