• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

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

    二、解题思路

    Step1.和二分查找法一样,我们用两个指针分别指向数组的第一个元素和最后一个元素。

    Step2.接着我们可以找到数组中间的元素:

    如果该中间元素位于前面的递增子数组,那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素,这样可以缩小寻找的范围。如果中间元素位于后面的递增子数组,那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。

    Step3.接下来我们再用更新之后的两个指针,重复做新一轮的查找。

    三、解题代码

    1. public class Test {
    2. /**
    3. * @param numbers 旋转数组
    4. * @return 数组的最小值
    5. */
    6. public static int min(int[] numbers) {
    7. // 判断输入是否合法
    8. if (numbers == null || numbers.length == 0) {
    9. throw new RuntimeException("Invalid input.");
    10. }
    11. // 开始处理的第一个位置
    12. int lo = 0;
    13. // 开始处理的最后一个位置
    14. int hi = numbers.length - 1;
    15. // 设置初始值
    16. int mi = lo;
    17. // 确保lo在前一个排好序的部分,hi在排好序的后一个部分
    18. while (numbers[lo] >= numbers[hi]) {
    19. // 当处理范围只有两个数据时,返回后一个结果
    20. // 因为numbers[lo] >= numbers[hi]总是成立,后一个结果对应的是最小的值
    21. if (hi - lo == 1) {
    22. return numbers[hi];
    23. }
    24. // 取中间的位置
    25. mi = lo + (hi - lo) / 2;
    26. // 如果三个数都相等,则需要进行顺序处理,从头到尾找最小的值
    27. if (numbers[mi] == numbers[lo] && numbers[hi] == numbers[mi]) {
    28. return minInorder(numbers, lo, hi);
    29. }
    30. // 如果中间位置对应的值在前一个排好序的部分,将lo设置为新的处理位置
    31. if (numbers[mi] >= numbers[lo]) {
    32. lo = mi;
    33. }
    34. // 如果中间位置对应的值在后一个排好序的部分,将hi设置为新的处理位置
    35. else if (numbers[mi] <= numbers[hi]) {
    36. hi = mi;
    37. }
    38. }
    39. // 返回最终的处理结果
    40. return numbers[mi];
    41. }
    42. /**
    43. * 找数组中的最小值
    44. *
    45. * @param numbers 数组
    46. * @param start 数组的起始位置
    47. * @param end 数组的结束位置
    48. * @return 找到的最小的数
    49. */
    50. public static int minInorder(int[] numbers, int start, int end) {
    51. int result = numbers[start];
    52. for (int i = start + 1; i <= end; i++) {
    53. if (result > numbers[i]) {
    54. result = numbers[i];
    55. }
    56. }
    57. return result;
    58. }
    59. }