宜宾网站建设公司

使用Java怎么查找旋转数组中的最小数字

本文章向大家介绍使用Java怎么查找旋转数组中的最小数字的基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

十多年的达日网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。营销型网站的优势是能够根据用户设备显示端的尺寸不同，自动调整达日建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。成都创新互联公司从事“达日网站设计”,“达日网站推广”以来，每个客户项目都认真落实执行。

Java是什么

Java是一门面向对象编程语言，可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序。

代码实现如下：

public class Test08 {

  public static int getTheMin(int nums[]) {
    if (nums == null || nums.length == 0) {
      throw new RuntimeException("input error!");
    }
    int result = nums[0];
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i + 1] < nums[i]) {
        result = nums[i + 1];
        break;
      }
    }
    return result;
  }

  public static void main(String[] args) {
    // 典型输入，单调升序的数组的一个旋转
    int[] array1 = {3, 4, 5, 1, 2};
    System.out.println(getTheMin(array1));

    // 有重复数字，并且重复的数字刚好的最小的数字
    int[] array2 = {3, 4, 5, 1, 1, 2};
    System.out.println(getTheMin(array2));

    // 有重复数字，但重复的数字不是第一个数字和最后一个数字
    int[] array3 = {3, 4, 5, 1, 2, 2};
    System.out.println(getTheMin(array3));

    // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
    int[] array4 = {1, 0, 1, 1, 1};
    System.out.println(getTheMin(array4));

    // 单调升序数组，旋转0个元素，也就是单调升序数组本身
    int[] array5 = {1, 2, 3, 4, 5};
    System.out.println(getTheMin(array5));

    // 数组中只有一个数字
    int[] array6 = {2};
    System.out.println(getTheMin(array6));

    // 数组中数字都相同
    int[] array7 = {1, 1, 1, 1, 1, 1, 1};
    System.out.println(getTheMin(array7));
  }
}

打印结果没什么毛病。不过这样的方法显然不是最优的，我们看看有没有办法找出更加优质的方法处理。

有序，还要查找？

找到这两个关键字，我们不免会想到我们的二分查找法，但不少小伙伴肯定会问，我们这个数组旋转后已经不是一个真正的有序数组了，不过倒像是两个递增的数组组合而成的，我们可以这样思考。

我们可以设定两个下标 low 和 high，并设定 mid = (low + high)/2，我们自然就可以找到数组中间的元素 array[mid]，如果中间的元素位于前面的递增数组，那么它应该大于或者等于 low 下标对应的元素，此时数组中最小的元素应该位于该元素的后面，我们可以把 low 下标指向该中间元素，这样可以缩小查找的范围。

同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于 high 下标对应的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们就可以把 high 下标更新到中位数的下标，这样也可以缩小查找的范围，移动之后的 high 下标对应的元素仍然在后面的递增子数组中。

不管是更新 low 还是 high，我们的查找范围都会缩小为原来的一半，接下来我们再用更新的下标去重复新一轮的查找。直到最后两个下标相邻，也就是我们的循环结束条件。

说了一堆，似乎已经绕的云里雾里了，我们不妨就拿题干中的这个输入来模拟验证一下我们的算法。

  1. input：{3，4，5，1，2}

  2. 此时 low = 0，high = 4，mid = 2，对应的值分别是：num[low] = 3，num[high] = 2，num[mid] = 5

  3. 由于 num[mid] > num[low]，所以 num[mid] 应该是在左边的递增子数组中。

  4. 更新 low = mid = 2，num[low] = 5，mid = (low+high)/2 = 3，num[mid] = 1;

  5. high - low ≠ 1 ，继续更新

  6. 由于 num[mid] < num[high]，所以断定 num[mid] = 1 位于右边的自增子数组中；

  7. 更新 high = mid = 3，由于 high - mid = 1,所以结束循环，得到最小值 num[high] = 1;

我们再来看看 Java 中如何用代码实现这个思路：

public class Test08 {

  public static int getTheMin(int nums[]) {
    if (nums == null || nums.length == 0) {
      throw new RuntimeException("input error!");
    }
    // 如果只有一个元素，直接返回
    if (nums.length == 1)
      return nums[0];
    int result = nums[0];
    int low = 0, high = nums.length - 1;
    int mid;
    // 确保 low 下标对应的值在左边的递增子数组，high 对应的值在右边递增子数组
    while (nums[low] >= nums[high]) {
      // 确保循环结束条件
      if (high - low == 1) {
        return nums[high];
      }
      // 取中间位置
      mid = (low + high) / 2;
      // 代表中间元素在左边递增子数组
      if (nums[mid] >= nums[low]) {
        low = mid;
      } else {
        high = mid;
      }
    }
    return result;
  }

  public static void main(String[] args) {
    // 典型输入，单调升序的数组的一个旋转
    int[] array1 = {3, 4, 5, 1, 2};
    System.out.println(getTheMin(array1));

    // 有重复数字，并且重复的数字刚好的最小的数字
    int[] array2 = {3, 4, 5, 1, 1, 2};
    System.out.println(getTheMin(array2));

    // 有重复数字，但重复的数字不是第一个数字和最后一个数字
    int[] array3 = {3, 4, 5, 1, 2, 2};
    System.out.println(getTheMin(array3));

    // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
    int[] array4 = {1, 0, 1, 1, 1};
    System.out.println(getTheMin(array4));

    // 单调升序数组，旋转0个元素，也就是单调升序数组本身
    int[] array5 = {1, 2, 3, 4, 5};
    System.out.println(getTheMin(array5));

    // 数组中只有一个数字
    int[] array6 = {2};
    System.out.println(getTheMin(array6));

    // 数组中数字都相同
    int[] array7 = {1, 1, 1, 1, 1, 1, 1};
    System.out.println(getTheMin(array7));

    // 特殊的不知道如何移动
    int[] array8 = {1, 0, 1, 1, 1};
    System.out.println(getTheMin(array8));
  }
}

前面我们提到在旋转数组中，由于是把递增排序数组的前面的若干个数字搬到数组后面，因为第一个数字总是大于或者等于最后一个数字，而还有一种特殊情况是移动了 0 个元素，即数组本身，也是它自己的旋转数组。这种情况本身数组就是有序的了，所以我们只需要返回第一个元素就好了，这也是为什么我先给 result 赋值为 nums[0] 的原因。

上述代码就完美了吗？我们通过测试用例并没有达到我们的要求，我们具体看看 array8 这个输入。先模拟计算机运行分析一下：

  1. low = 0, high = 4, mid = 2, nums[low] = 1, nums[high] = 1,nums[mid] = 1;

  2. 由于 nums[mid] >= nums[low]，故认定 nums[mid] = 1 在左边递增子数组中；

  3. 所以更新 high = mid = 2,mid = (low+high)/2 = 1;

  4. nums[low] = 1,nums[mid] = 1,nums[high] = 1;

  5. high - low ≠ 1，继续循环；

  6. 由于 nums[mid] >= nums[low]，故认定 nums[mid] = 1 在左边递增子数组中；

  7. 所以更新 high = mid = 1,由于 high - low = 1,故退出循环，得到 result = 1；

但我们一眼了然，明显我们的最小值不是 1 ，而是 0 ，所以当 array[low]、array[mid]、array[high] 相等的时候，我们的程序并不知道应该如何移动，按照目前的移动方式就默认 array[mid] 在左边递增子数组了，这显然是不负责任的做法。

我们修正一下代码：

public class Test08 {

  public static int getTheMin(int nums[]) {
    if (nums == null || nums.length == 0) {
      throw new RuntimeException("input error!");
    }
    // 如果只有一个元素，直接返回
    if (nums.length == 1)
      return nums[0];
    int result = nums[0];
    int low = 0, high = nums.length - 1;
    int mid = low;
    // 确保 low 下标对应的值在左边的递增子数组，high 对应的值在右边递增子数组
    while (nums[low] >= nums[high]) {
      // 确保循环结束条件
      if (high - low == 1) {
        return nums[high];
      }
      // 取中间位置
      mid = (low + high) / 2;
      // 三值相等的特殊情况，则需要从头到尾查找最小的值
      if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
        return midInorder(nums, low, high);
      }
      // 代表中间元素在左边递增子数组
      if (nums[mid] >= nums[low]) {
        low = mid;
      } else {
        high = mid;
      }
    }
    return result;
  }

  /**
   * 查找数组中的最小值
   *
   * @param nums 数组
   * @param start 数组开始位置
   * @param end  数组结束位置
   * @return 找到的最小的数字
   */
  public static int midInorder(int[] nums, int start, int end) {
    int result = nums[start];
    for (int i = start + 1; i <= end; i++) {
      if (result > nums[i])
        result = nums[i];
    }
    return result;
  }

  public static void main(String[] args) {
    // 典型输入，单调升序的数组的一个旋转
    int[] array1 = {3, 4, 5, 1, 2};
    System.out.println(getTheMin(array1));

    // 有重复数字，并且重复的数字刚好的最小的数字
    int[] array2 = {3, 4, 5, 1, 1, 2};
    System.out.println(getTheMin(array2));

    // 有重复数字，但重复的数字不是第一个数字和最后一个数字
    int[] array3 = {3, 4, 5, 1, 2, 2};
    System.out.println(getTheMin(array3));

    // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
    int[] array4 = {1, 0, 1, 1, 1};
    System.out.println(getTheMin(array4));

    // 单调升序数组，旋转0个元素，也就是单调升序数组本身
    int[] array5 = {1, 2, 3, 4, 5};
    System.out.println(getTheMin(array5));

    // 数组中只有一个数字
    int[] array6 = {2};
    System.out.println(getTheMin(array6));

    // 数组中数字都相同
    int[] array7 = {1, 1, 1, 1, 1, 1, 1};
    System.out.println(getTheMin(array7));

    // 特殊的不知道如何移动
    int[] array8 = {1, 0, 1, 1, 1};
    System.out.println(getTheMin(array8));

  }
}

以上就是小编为大家带来的使用Java怎么查找旋转数组中的最小数字的全部内容了，希望大家多多支持创新互联！


分享文章：使用Java怎么查找旋转数组中的最小数字
文章来源：http://hbruida.cn/article/ipiges.html

其他资讯