Monday, September 21, 2015

LeetCode OJ - Find Minimum in Rotated Sorted Array

Problem:

Please find the problem here.

Solution:

This is a divide and conquer algorithm, the key observation is that if an array with no duplicate element is rotated, its first value must be larger than the last value.

Divide the array into halves and ALWAYS include the middle element, we can conclude either

  1. The array is not rotated at all, just return the first element, or
  2. The array is rotated, and exactly one half is rotated and the another is not.
Pick the right half and recursively solve the problem. The base case of two elements is simple to solve.


Code:

#include "stdafx.h"

// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

#include "LEET_FIND_MINIMUM_IN_ROTATED_SORTED_ARRAY.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_FIND_MINIMUM_IN_ROTATED_SORTED_ARRAY
{
    class Solution {
    public:
        int findMin(vector<int>& nums)
        {
            int size = nums.size();
            if (size == 0)
            {
                // minimum is not defined for this case
                return -1;
            }
            else if (size == 1)
            {
                return nums[0];
            }
            else
            {
                int start = 0;
                int end = size;
                while (end > start)
                {
                    if (nums[start] < nums[end - 1])
                    {
                        return nums[start];
                    }
                    else
                    {
                        int length = end - start;
                        if (length == 2)
                        {
                            return nums[start + 1];
                        }
                        else
                        {
                            int mid = (start + end) / 2;
                            if (nums[start] > nums[mid])
                            {
                                end = mid + 1;
                            }
                            else
                            {
                                // nums[start] > nums[end - 1]
                                // nums[start] < nums[mid]
                                // => nums[end - 1] < nums[start] < nums[mid]
                                start = mid;
                            }
                        }
                    }
                }
            }
            
            return -1;
        }
    };
};

using namespace _LEET_FIND_MINIMUM_IN_ROTATED_SORTED_ARRAY;

int LEET_FIND_MINIMUM_IN_ROTATED_SORTED_ARRAY()
{
    int case1[] = { 4, 5, 6, 7, 0, 1, 2 };
    Solution s;
    cout << s.findMin(vector<int>(case1, case1 + _countof(case1))) << endl;
    return 0;
}

No comments :

Post a Comment