设为首页 加入收藏

TOP

C++ 和 Python 实现旋转数组的最小数字(一)
2019-02-07 22:08:02 】 浏览:133
Tags:Python 实现 旋转 最小 数字

  把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转,该数组的最小值为 1 。


1. 暴力查找(Bruteforce Search):把旋转数组从前到后遍历一遍,其时间复杂度为 O(n)。很明显,这种思想非常直接粗暴,没有用到旋转数组的性质。


2. 二分查找(Binary Search):每次查找都把旋转数组平均分成两部分,通过比较当前旋转数组两端点中间点的值,判断最小值在数组的哪一部分,从而达到缩小搜索范围的目的。其中,两端点为当前的旋转数组索引最小索引最大的元素,中间点为这两部分子数组的连结元素,也可以看做为轴枢点(pivot point),这里取旋转数组的最小索引和最大索引的算术平均值(向下取整)作为索引,其对应的元素作为中间点。具体过程,如图 2.10 所示。



需要注意,当旋转数组的两端点的值都与中间点的值相等时,因为无法判断最小值在哪一部分,因此需要采用顺序查找方法,即暴力查找。其示例如图 2.11 所示。



#include <stdio.h>
#include <exception>
#include <iostream>


// Declare a parameter exception
class ParamException: public std::exception {
    virtual const char* what() const throw()
    {
        return "Error: input parameters exception!";
    }
};


// find minimum in data[staIndex..endIndex]
int findMinInRotatedArray(int data[], int staIndex, int endIndex)
{
    if (staIndex > endIndex || data == NULL)
    {
        throw ParamException();
    }


    int minimum = data[staIndex];


    if (data[staIndex] >= data[endIndex] && staIndex < endIndex - 1)  // 易错点
    {
        // Use Binary Search
        int midIndex = (staIndex + endIndex) / 2;


        if (data[midIndex] > data[staIndex])
            minimum = findMinInRotatedArray(data, midIndex, endIndex);
        else if (data[midIndex] < data[endIndex])
            minimum = findMinInRotatedArray(data, staIndex, midIndex);
        else
        {
            // Find the minimum sequentially
            for (int i = staIndex+1; i <= endIndex; ++i)
                if (minimum > data[i])
                    minimum = data[i];
        }
    }
    else if (staIndex == (endIndex - 1))
    {
        minimum = data[staIndex] > data[endIndex]? data[endIndex]:data[staIndex];
    }


    return minimum;
}


void unitest()
{
    int arr1[] = {3, 4, 5, 1, 2};
    int arr2[] = {1, 0, 1, 1, 1};
    int arr3[] = {1, 1, 1, 0, 1};
    int arr4[] = {1, 2, 3, 4, 5};


    printf("The minimum of the rotated array {3, 4, 5, 1, 2} is %d.\n", findMinInRotatedArray(arr1, 0, 4));
    printf("The minimum of the rotated array {1, 0, 1, 1, 1} is %d.\n", findMinInRotatedArray(arr2, 0, 4));
    printf("The minimum of the rotated array {1, 1, 1, 0, 1} is %d.\n", findMinInRotatedArray(arr3, 0, 4));
    printf("The minimum of the rotated array {1, 2, 3, 4, 5} is %d.\n", findMinInRotatedArray(arr4, 0, 4));



    // Test index parameter exception
    try {
        findMinInRotatedArray(arr3, 5, 4);
    }
    catch(std::exception& e) {
        std::cout << e.what() << std::endl;
    };
}


int main(void)
{
    unitest();


    return 0;
}


C++ 和 Python 实现旋转数组的最小数字


#!/usr/bin/pyth
编程开发网

首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++ STL容器——stack用法介绍 下一篇C++随机排序容器中的元素

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }