5

我最近遇到了一个编程问题，如下所示：

给出了一个排序数组，并且数组在某个未知点旋转，我必须找到其中的最小元素。数组也可以包含重复项。

例如：

 Input: {5, 6, 1, 2, 3, 4}

 Output: 1  

 Input: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2}   

 Output: 0

我遵循简单的解决方案是遍历整个数组并找到最小值。这个解决方案需要时间 O(n)。我理解最小元素是前一个元素大于它的元素。如果不存在这样的元素，则没有旋转，第一个元素将是最小值。

但我被要求提供 O(Logn) 解决方案。有没有办法在 O(Logn) 时间内解决它？

4

3 回答 3

11

在我的头顶上：

  • 注意第一个条目
  • 执行二分查找；在每个阶段，如果枢轴元素大于或等于存储的第一个元素，则选择右半部分，如果枢轴元素小于则选择左半部分。

例如，给定{4,5,6,7,1,2,3}：

  • 以7>为轴心4，减少到右半部分{1,2,3}
  • 以2<为轴心4，减少到左半部分1。
  • 只考虑一个元素，答案是1。
于 2013-07-02T16:21:54.847 回答
1

看到这个：因为它是排序数组。我需要应用二进制搜索来找到枢轴..

最低元素将是数组旋转的位置。

调用这个findpivot(arr,0,n-1);

int findPivot(int arr[], int low, int high)
{
   // base cases
   if (high < low)  return -1;
   if (high == low) return low;

   int mid = (low + high)/2;   /*low + (high - low)/2;*/
   if (mid < high && arr[mid] > arr[mid + 1])
     return mid;
   if (mid > low && arr[mid] < arr[mid - 1])
     return (mid-1);
   if (arr[low] >= arr[mid])
     return findPivot(arr, low, mid-1);
   else
     return findPivot(arr, mid + 1, high);
}
于 2013-07-02T16:23:42.820 回答
0 
public class MinElementInRotatedArrayUsingRecursion {

    public static void main(String[] args) {
        int arr1[] = { 5, 6, 1, 2, 3, 4 };
        int n1 = arr1.length;
        System.out.println("The minimum element is " + findMin(arr1));

        int arr2[] = { 1, 2, 3, 4 };
        int n2 = arr2.length;
        System.out.println("The minimum element is " + findMin(arr2));

        int arr3[] = { 1 };
        int n3 = arr3.length;
        System.out.println("The minimum element is " + findMin(arr3));

        int arr4[] = { 1, 2 };
        int n4 = arr4.length;
        System.out.println("The minimum element is " + findMin(arr4));

        int arr5[] = { 2, 1 };
        int n5 = arr5.length;
        System.out.println("The minimum element is " + findMin(arr5));

        int arr6[] = { 5, 6, 7, 1, 2, 3, 4 };
        int n6 = arr6.length;
        System.out.println("The minimum element is " + findMin(arr6));

        int arr7[] = { 1, 2, 3, 4, 5, 6, 7 };
        int n7 = arr7.length;
        System.out.println("The minimum element is " + findMin(arr7));

        int arr8[] = { 2, 3, 4, 5, 6, 7, 8, 1 };
        int n8 = arr8.length;
        System.out.println("The minimum element is " + findMin(arr8));

        int arr9[] = { 3, 4, 5, 1, 2 };
        int n9 = arr9.length;
        System.out.println("The minimum element is " + findMin(arr9));

    }// main

    public static int findMin(int[] num) {
        return findMin(num, 0, num.length - 1);
    }

    public static int findMin(int[] num, int start, int last) {
        // only 1 element
        if (start == last)
            return num[start];
        // only 2 elements
        if ((last - start) == 1)
            return Math.min(num[start], num[last]);

        int middle = start + (last - start) / 2;

        // not rotated
        if (num[start] < num[last]) {
            return num[start];
        }

        // go last side
        /*
         * int[] a = 2,3,4,5,1
         *  a[start]=2 and a[last]=1 and a[mid] = 4 
         *  a[mid] > a[start]
         * Then, as the array is rotated, That's why, calculation will start from
         * a[middle] to a[last]
         */
        else if (num[middle] > num[start]) {
            return findMin(num, middle, last);
        } else {

            // go start side
            /*
             * int[] a = 4,5,1,2,3 
             * a[start]= 4 and a[last]=3 and a[mid] = 1 
             * a[mid] < a[start]
             * Then, as the array is rotated, That's why, calculation will start from
             * a[start] to a[middle]
             */
            return findMin(num, start, middle);
        }
    }
}

迭代方法：

public class MinElementInRotatedArrayUsingRecursionAndIteration {

    public static void main(String[] args) {
        int arr1[] = { 5, 6, 1, 2, 3, 4 };
        int n1 = arr1.length;
        System.out.println("The minimum element is " + findMin(arr1));

        int arr2[] = { 1, 2, 3, 4 };
        int n2 = arr2.length;
        System.out.println("The minimum element is " + findMin(arr2));

        int arr3[] = { 1 };
        int n3 = arr3.length;
        System.out.println("The minimum element is " + findMin(arr3));

        int arr4[] = { 1, 2 };
        int n4 = arr4.length;
        System.out.println("The minimum element is " + findMin(arr4));

        int arr5[] = { 2, 1 };
        int n5 = arr5.length;
        System.out.println("The minimum element is " + findMin(arr5));

        int arr6[] = { 5, 6, 7, 1, 2, 3, 4 };
        int n6 = arr6.length;
        System.out.println("The minimum element is " + findMin(arr6));

        int arr7[] = { 1, 2, 3, 4, 5, 6, 7 };
        int n7 = arr7.length;
        System.out.println("The minimum element is " + findMin(arr7));

        int arr8[] = { 2, 3, 4, 5, 6, 7, 8, 1 };
        int n8 = arr8.length;
        System.out.println("The minimum element is " + findMin(arr8));

        int arr9[] = { 3, 4, 5, 1, 2 };
        int n9 = arr9.length;
        System.out.println("The minimum element is " + findMin(arr9));

    }// main

    // iterative method
    public static int findMin(int[] nums) {


        int start =0; 
        int last =nums.length-1;

        while(start <= last){
            if(nums[start]<=nums[last]) return nums[start];

            int mid =(start + last)/2;
            /*  int[] a =  2,3,4,5,1
             a[start]=2 and a[last]=1
             a[mid] = 4
             a[mid] > a[start] 
            Then, as the array is rotated, That's why, calculation will start from a[middle] to a[last]
    */
            if(nums[mid]>=nums[start]){
                start = mid +1;
            }else{
                /*  int[] a =  4,5,1,2,3
             a[start]= 4 and a[last]=3
             a[mid] = 1
             a[mid] < a[start] 
            Then, as the array is rotated, That's why, calculation will start from a[start] to a[middle]
       */
                last = mid;
            }
        }

        return -1;
    }

}
于 2019-03-07T08:22:46.433 回答