【58同城2017年笔试题】找到局部有序的数组的最小值，复杂度为O(logn)

本文主要是介绍【58同城2017年笔试题】找到局部有序的数组的最小值，复杂度为O(logn)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

对升序的排列的整数数组连续取前N个元素进行逆序排列，得到局部有序的数组，如：

【1,2,3,4,5,6】->【4,3,2,1,5,6】

假设数组元素无重复，从这种局部有序的数组中找到最小值，要求时间复杂度小于O(n)，空间复杂度为O(1)

解题思路：

①找到数组的中间位置mid的值，将mid的左右两边的值进行比较；
②取mid和左右两边比较的小的一边，舍弃另一边；
③直到在限定范围内的数只有两个的时候，小的那个就是最小值

就拿【4,3,2,1,5,6】为例，①mid=2位置的值为2，比较其左右两边的值；②右边小，那么舍弃左边，保留右边为【2,1,5,6】；重复第一二步，为【2,1】；

③那么小的那个即为最小值，为1
这种策略的算法复杂度为O(logn),空间复杂度为O(1)，满足题目要求。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNext()){String str= in.nextLine();String[] str1 = str.split(" ");int[] arr= new int[str1.length];for(int i=0; i<arr.length; i++){arr[i] = Integer.parseInt(str1[i]);}int ret = findMin(arr, arr.length);System.out.println("最小的数为：" + ret);}}static int findMin(int arr[], int arrLen){int min = 0;int i=0, j=arrLen-1, mid=(arrLen-1)/2;while(j-i>1){// 舍弃前半段if(arr[mid-1] > arr[mid+1]){i=mid;}else if(arr[mid-1] < arr[mid+1]){// 舍弃后半段j=mid;}mid = (i + j)/2;}if(arr[i]>arr[j])min=arr[j];elsemin=arr[i];return min;}
}