龙空技术网

「剑指Offer」 06. 旋转数组的最小数字

柚子树cc 160

前言:

眼前各位老铁们对“数组排序python”大约比较关注,你们都需要知道一些“数组排序python”的相关知识。那么小编也在网络上搜集了一些对于“数组排序python””的相关资讯,希望大家能喜欢,看官们一起来学习一下吧!

1、题目描述

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

示例 1:输入:[3,4,5,1,2]输出:1示例 2:输入:[2,2,2,0,1]输出:0
2、C++
/* 2020-9-5 DuYong */class Solution {public:    int minArray(vector<int>& numbers) {        // 1. STL方法        // return *min_element(numbers.begin(), numbers.end());        // 2. 二分查找 + 顺序查找        size_t left = 0;        size_t right = numbers.size() - 1;        size_t mid = left;        while (numbers[left] >= numbers[right]) {            if ((right - left) == 1) {                mid = right;                break;            }            mid = (left + right) / 2;            if (numbers[left]==numbers[mid] && numbers[mid]==numbers[right]) {                // 当前序列无法正确划分,采用顺序查找                return minSearch(numbers, left, right);            }            else if (numbers[mid] >= numbers[left]) {                left = mid;            }            else if (numbers[mid] <= numbers[right]) {                right = mid;            }        }        return numbers[mid];    }    // 顺序查找    int minSearch(vector<int>& numbers, int left, int right) {        int min = numbers[left];        for (size_t i = left+1; i <= right; i++) {            if (min > numbers[i]) {                min = numbers[i];            }        }        return min;    }};
3、Python
class Solution:    def minArray(self, numbers: List[int]) -> int:        return min(numbers)

标签: #数组排序python