2016年小米校招筆試第二題（西安站）

2 現(xiàn)有一個數(shù)組是由有序數(shù)組經(jīng)過n次循環(huán)移動后所得，請你用最快速度查找某個元素位置（如1234568，向右移動3次后為67812345）。

參考解法（Java版）：

看題后第一直覺可能想去遍歷數(shù)組，那么時間復(fù)雜度為o(n)，不夠高效。下面提供另一種參考方法。

package XiaoMi; /********************************************************* 解題思路：首先找到轉(zhuǎn)折點，從轉(zhuǎn)折點截斷，原數(shù)組分成兩個有序數(shù)組；* 再利用二分查找對兩段分別查找，最終返回查找結(jié)果。其中，對二分查* 找算法做了一些改進，加了兩個起始位、結(jié)束位兩個參數(shù)，使用中更方便。* *****************************************************/ import java.util.Arrays;public class test14 {/*** @param args*/private final static String str = "67812345";public static void main(String[] args) {// TODO Auto-generated method stubfind(str, 3);}public static int find(String str, int in) {// 將String輸入轉(zhuǎn)換為int數(shù)組char[] chars = str.toCharArray();int[] ints = new int[chars.length];int i = 0;for (char x : chars) {//ints[i] = Integer.valueOf(x);ints[i] =Integer.parseInt(x+""); //字符串轉(zhuǎn)int型//System.out.println(ints[i]);++i;}// 查找排序轉(zhuǎn)折點int j = 0;while (!(ints[j] >= ints[j + 1])) {++j;}// 將數(shù)組從轉(zhuǎn)折點截為兩段有序數(shù)組，再運用二分查找int loc =0;if (in > ints[ints.length - 1]) { // 在左邊loc =binarySearch(ints, in, 0, j);} else { // 在右邊loc =binarySearch(ints, in, j+1, ints.length - 1);}System.out.println(loc);return 0;}// 改進二分查找public static int binarySearch(int[] src, int des, int start, int end) {int low = start;int high = end;while ((low <= high)){int middle = low + ((high - low) >> 1);if (des == src[middle]) {return middle;} else if (des < src[middle]) {high = middle - 1;} else {low = middle + 1;}}return -1;} } 運行結(jié)果：

5

總結(jié)

以上是生活随笔為你收集整理的【小米校招笔试】一个数组是由有序数组经过n次循环移动后所得，请你用最快速度查找某个元素位置的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。