有序数组arr可能经过一次旋转处理,也可能没有,且arr可能存在重复的数。例如,有序数组[1, 2, 3, 4, 5, 6, 7],可以旋转处理成[4, 5, 6, 7, 1, 2, 3]等。给定一个可能旋转过的有序数组arr,返回arr中的最小值。
[要求]
期望复杂度为
第一行一个整数N表示数组大小。
接下来N个数表示数组内的数。
输出一个整数表示答案
7 1 2 3 4 5 6 7
1
7 4 5 6 7 1 2 3
1
import java.util.Scanner; public class Main { public static int find(int p, int r, int n, int arr[]) { while (p <= r) { int mid = p + (r - p) / 2; if (arr[p] <= arr[mid] && arr[mid] <= arr[r]) { return (arr[p] <= arr[mid + 1] ? arr[p] : arr[mid + 1]); } else if (arr[p] <= arr[mid]) { p = mid + 1; } else if (arr[mid] <= arr[r]) { r = mid - 1; } } return 0; } public static void main(String[] args) { int n = 0; int arr[] = new int[10000000]; Scanner sc = new Scanner(System.in); n = sc.nextInt(); for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } System.out.println(find(0, n - 1, n, arr)); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().trim().split(" "); int[] arr = new int[n]; for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]); int left = 0, right = n - 1; while(left < right) { if(arr[left] < arr[right]) break; int mid = left + (right - left) / 2; if(arr[mid] > arr[right]){ left = mid + 1; }else right = mid; } System.out.println(arr[left]); } }
#include<bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n) { vector<int> vc(n+1,0); for(int i=0;i<n;i++) { cin>>vc[i]; } int low=0,high=n-1,mid=0; while(low<high) { if(vc[low]<vc[high]) {//这里是严格升序,所以直接可以返回,每次是在low-high这个范围里找最小值 break; } mid=(low+high)/2; if(vc[low]<=vc[mid])// 2 2 2 2 1 2 {//说明vc[low -mid]这一段是非降序的,表明min不在这里 low=mid+1; } else {//vc[low] > vc[mid],最小值肯定在 low - mid范围内 high=mid; } } cout<<vc[low]<<endl; } return 0; }
import java.util.Scanner; import java.util.Arrays; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] arr=new int[n]; for(int i=0;i<n;i++){ arr[i]=sc.nextInt(); } Arrays.sort(arr); System.out.print(arr[0]); } }
int findMinimumInRotatedSortedArray(const vector& arr) { if (arr.size() == 1) return arr[0]; int L = 0, R = arr.size()-1; while (L <= R) { if (arr[R] >= arr[L]) return arr[L]; int mid = (L + R) / 2; if (mid + 1 <= R && arr[mid+1] < arr[mid]) return arr[mid+1]; if (mid - 1 >= L && arr[mid-1] > arr[mid]) return arr[mid]; if (arr[mid] > arr[L]) L = mid+1; else R = mid-1; } return arr[L]; }
测资好像不是很足够,上面的代码可以通过,试试[3, 1, 3]發现答案不是正确的