Tuesday, December 30, 2014

LeetCode Rotated Sorted Array Problems

There are 4 problems about rotated sorted array, the sorted array is like [0 , 1, 2, 3, 4, 5], and the rotated sorted array is separating the sorted array to two parts and exchange the position of them. So one rotated array of above is [3, 4, 5, 0, 1, 2]. The fist two problems is Search in Rotated Sorted Array and Search in Rotated Sorted Array II. The difference is the first one's array have no duplicate and the second one may have duplicated elements. The method to solve the two question is the same. Here is the code for first question:

int search(int A[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    int mid;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (target == A[mid]) {
            return mid;
        }
        if (A[lo] < A[mid]) {// target in left part, when no duplicate, change "<" to "<=".
            if (A[lo] <= target && target <= A[mid]) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }
        else if (A[lo] > A[mid]) { //target in right part. when no duplicate, change to else here.
            if (A[mid] <= target && target <= A[hi]) {
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        else { // handle duplicated cases
            lo++;
        }
    }
    return -1;
}

In fact, the code above also could handle the cases contain duplicated elements. When there are duplicated elements, we do know target in which part, so just let "lo" increase by one. If there have no duplicates, the time complexity is O(logn), just like binary search for a sorted array. if there are duplicated cases, the worst time complexity is O(n) for a array like [3, 3, 3, 3, 1, 3, 3].

The other two problem is Find Minimum in Rotated Sorted Array and Find Minimum in Rotated Sorted Array II. These two questions also could use binary search to solve, and just like the above two problems, the difference is whether there are duplicated elements. Here is the code:

int findMin(vector<int> &num) {
    int lo = 0;
    int hi = num.size() - 1;
    int mid = 0;

    while(lo < hi) {
        mid = lo + (hi - lo) / 2;

        if (num[mid] > num[hi]) { //minimum in right side
            lo = mid + 1;
        }
        else if (num[mid] < num[hi]) { //mininum in left side
            hi = mid;
        }
        else { // when num[mid] and num[hi] are same
            hi--;
        }
    }
    return num[lo];
}

Just as first two questions, this could handle the duplicated elements. This part of problems compare middle elements with "hi" elements, we also could compare middle and "lo" elements.

Written with StackEdit.

1 comment:



  1. Nhạc Thành nhìn Tôn Thi Thi mỉm cười nói.

    - Hiểu Kỳ tỷ, Thi Thi, các ngươi làm thế nào tới được đây, thật tốt.

    Đông Phương Lạc Nhan đi tới bên người Yến Hiểu Kỳ cùng Tôn Thi Thi nói, mặc dù ba cô gái này thời gian gặp nhau cũng không dài, nhưng bởi vì quan hệ với Nhạc Thành, ba cô gái này cũng tín nhiệm lẫn nhau.

    - Ừ, Lạc Nhan, làm sao ngươi cũng có ở đây.

    Yến Hiểu Kỳ cùng Tôn Thi Thi lập tức cùng với Đông Phương Lạc Nhan hàn huyên.
    dongtam
    mu moi ra hom nay
    tim phong tro
    http://nhatroso.com/
    nhạc sàn
    tổng đài tư vấn luật
    văn phòng luật hà nội
    tổng đài tư vấn luật
    thành lập công ty trọn gói
    http://we-cooking.com/
    chém gió
    trung tâm tiếng anh
    - Tộc trưởng, ngươi làm sao lại ở chỗ này, mãnh thú là các ngươi giết sao.

    Nhạc Siêu nhìn Nhạc Thành thi lễ, lập tức nhìn thấy phía trước là thi thể ma thú, kinh ngạc hỏi.

    - Ừ, là chúng ta vừa mới giết.

    Nhạc Thành trả lời.

    - Tộc trưởng là không tốt, chúng ta lập tức rời đi mới được.

    Nhạc Siêu sắc mặt đột nhiên thay đổi, tựa hồ là e ngại cái gì đó vậy.

    ReplyDelete