LinkedIn 电面

两种情况， 有duplicate or not

第二题要注意没有rotate的情况。也就是给你array 【1，2，3，4，5，6，7】找rotate的点

第一题要注意Duplicates or not，写之前沟通好就行。我写了一个，是否有Duplicates都可以处理，通过LeetCode.

    public static boolean findSearchInRotatedSortedArray(int[] A, int target) {
        if (A == null || A.length < 1)
            return false;
        
        int L = 0;
        int R = A.length - 1;
        
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] == target)
                return true;
            
            if (A[L] < A[M]) {
                if (A[L] <= target && target < A[M]) {
                    R = M - 1;
                } else {
                    L = M + 1;
                }
            } else if (A[L] > A[M]){
                if (A[M] < target && target <= A[R]) {
                    L = M + 1;
                } else {
                    R = M - 1;
                }
            } else {
                L++;
            }
        }
        return false;
    }

刚才的代码未能正常显示

1. public static boolean findSearchInRotatedSortedArray(int[] A, int target) {
   
2.         if (A == null || A.length < 1)
   
3.             return false;
   
4.         
   
5.         int L = 0;
   
6.         int R = A.length - 1;
   
7.         
   
8.         while (L <= R) {
   
9.             int M = (L + R) / 2;
   
10.             if (A[M] == target)
    
11.                 return true;
    
12.             
    
13.             if (A[L] < A[M]) {
    
14.                 if (A[L] <= target && target < A[M]) {
    
15.                     R = M - 1;
    
16.                 } else {
    
17.                     L = M + 1;
    
18.                 }
    
19.             } else if (A[L] > A[M]){
    
20.                 if (A[M] < target && target <= A[R]) {
    
21.                     L = M + 1;
    
22.                 } else {
    
23.                     R = M - 1;
    
24.                 }
    
25.             } else {
    
26.                 L++;
    
27.             }
    
28.         }
    
29.         return false;
    
30.     }

复制代码

第二题要注意duplicates，是否rotate，以下是我的code。

1.     public static int findSmallestElement(int[] A) {
   
2.         if (A == null || A.length < 2) // null, empty and one element.
   
3.             return 0;
   
4. 
   
5.         int L = 0;
   
6.         int R = A.length - 1;
   
7.         
   
8.         if (A[R] > A[L]) // No rotation.
   
9.             return A[L];
   
10. 
    
11.         while (L < R) {
    
12.             int M = (L + R) / 2;
    
13.             if (L == M)
    
14.                 return M + 1; // Finally the loop will reach L = M, then A[M + 1] should be the smallest element.
    
15.             
    
16.             if (A[L] < A[M]) { // Left is smaller than middle, then search the right half array including current middle element.
    
17.                 L = M; // Not L = M + 1.
    
18.             } else if (A[L] > A[M]) { // Left is greater than middle, then search the left half array including current middle element.
    
19.                 R = M; // Not R = M + 1.
    
20.             } else { // Left is the same as middle, just increment left pointer by one.
    
21.                 L++;
    
22.             }
    
23.         }
    
24.         return 0;
    
25.     }

复制代码

你是new grad吗

tiexiong 发表于 2014-8-1 03:08
第二题要注意duplicates，是否rotate，以下是我的code。

想确认下我题目理解的对不对，首先是sorted的array，其次是绕着某个pivot转了N次，最后我们也不知道是否rotate过。这样子遍历一遍数组，记录数组最后访问的最大值的index（有duplicates）情况，如果index == 数组length-1，返回0，否则返回index+1， 比如6， 7， 7， 1， 1， 2， 3， 最后访问的最大值7的index是2，这样rotate点位置就是3