面试题:Java 实现查找旋转数组的最小数字

在算法面试中,面试官总是喜欢围绕链表、排序、二叉树、二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流。而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员。所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要。

面试题:打印出旋转数组的最小数字

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

要想实现这个需求很简单,我们只需要遍历一遍数组,找到最小的值后直接退出循环。代码实现如下:

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));

  }
}

我们再用完善的测试用例放进去,测试通过。

总结

本题其实考察的点挺多的,实际上就是考察对二分查找的灵活运用,不少小伙伴死记硬背二分查找必须遵从有序,而没有学会这个二分查找的思想,这样会导致只能想到循环查找最小值了。

不少小伙伴在面试中表态,Android 原生态基本都封装了常用算法,对面试这些无作用的算法表示抗议,其实这是相当愚蠢的。我们不求死记硬背算法的实现,但求学习到其中巧妙的思想。只有不断地提升自己的思维能力,才能助自己收获更好的职业发展。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java对数组实现选择排序算法的实例详解

    一. 算法描述     选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟

  • 简单讲解奇偶排序算法及在Java数组中的实现

    奇偶排序是一个比较有个性的排序,基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序 举例吧, 待排数组 [6 2 4 1 5 9] 第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比 [6 2 4 1 5 9] 交换后变成 [2 6 1 4 5 9] 第二次比较偶数列,即6和1比,5和5比 [2 6 1 4 5 9] 交换后变成 [2 1 6 4 5 9] 第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较 [2 1 6 4 5 9] 交

  • Java数组常用排序算法实例小结

    本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo

  • Java查找不重复无序数组中是否存在两个数字的和为某个值

    今天去某在线教育面试面试官让做的一道题,题目描述如下: 给定一个不重复的无序数组arr和一个定值num 查找arr中是否有两个数的和等于num 有则返回这两个数的下标(可能有多组, 只用返回一组), 没有则返回null 很多人一想可能就是两层for循环,我想了很久最后写了双重for循环-[这个代码太easy就不放了]然后面试官说知道哈希吗,由于哈希查找的时间复杂度是O(1),从哈希的角度去考虑,这中间还有一堆就不描述了,说一下怎么用哈希实现. 实现思路: 将数组中的所有的值放入HashMap的K

  • java实现二分法查找出数组重复数字

    本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下 package offer; /** * 二分查找的思想来找到数组中重复的数字,时间复杂度在o(nlogn)-o(n^2) */ public class FindDuplicate3 { public static void main(String[] args) { int numbers[] = {0,1,2,3,4,4,6,7};//数组中的数 大小从0 到 numbers.length-1 f

  • Java数组高级算法与Arrays类常见操作小结【排序、查找】

    本文实例讲述了Java数组高级算法与Arrays类常见操作.分享给大家供大家参考,具体如下: 冒泡排序 冒泡排序原理 冒泡排序代码: package cn.itcast_01; /* * 数组排序之冒泡排序: * 相邻元素两两比较,大的往后放,第一次完毕,最大值出现在了最大索引处 */ public class ArrayDemo { public static void main(String[] args) { // 定义一个数组 int[] arr = { 24, 69, 80, 57,

  • Java算法实现调整数组顺序使奇数位于偶数之前的讲解

    调整数组顺序使奇数位于偶数之前 1. 题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变. 2. 题目分析 该题目类似于一个选择排序,将奇数选择出来,放置于数据前面的位置,保持其他未被选择的元素的相对位置不变: 1. 遍历数组,当数组元素为奇数是进行处理,判断条件为 n % 2 != 0 2. 设置一个变量标注当前已遍历的元素中奇数的个数oddNum,也是将该奇数元素

  • 详解Java数据结构和算法(有序数组和二分查找)

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • 面试题:Java 实现查找旋转数组的最小数字

    在算法面试中,面试官总是喜欢围绕链表.排序.二叉树.二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流.而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员.所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要. 面试题:打印出旋转数组的最小数字 题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该

  • 求解旋转数组的最小数字

    求解旋转数组的最小数字 题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小数组.例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的旋转数组,该数组的最小值为1. 思路解析: O(N)的算法 这种算法的思想就是遍历这个数组,由于这个数组是两部分有序的数组,因此遍历这个数组时当后一个数字小于前一个数字时,则后一个(即较小)一定为整个数组中最小的数字. 这种算法的思想很简单,但就是时间复杂度较大,因此不是很好的算

  • C++中求旋转数组中的最小数字(经典面试题)

    面试题:旋转数组的最小数字 题目:把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增数组的旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. 算法: (1)当输入的旋转数组非法时:处理! (2)当输入的旋转数组正常时,index1 = 0:index2=length-1: a:如果arry[index1] <arry[index2]时:说明数组为原数组,并没有进行旋转:    b:如果arry[ind

  • Java二分查找算法与数组处理的应用实例

    目录 1.特殊数组的特征值 题目描述 思路详解 代码与结果 2.在D天内送达包裹的能力 题目描述 思路详解 代码与结果 3.咒语和药水的成功对数 题目描述 思路详解 代码与结果 总结 1.特殊数组的特征值 题目描述 思路详解 看到本题,首先思考需要排序,然后查找,这里为了效率采用二分查找. 假设定义x=(left+riht)/ 2,每次查找到nums中第一个大于等于X的元素下标,判断大于等于X的个数与X的关系,进行分情况修改左右边界. 代码与结果 class Solution { public

  • Python划分数组为连续数字集合的练习

    目录 1.问题描述 2.解决方案 3.结语 本文转自微信公众号:"算法与编程之美" 1.问题描述 给你一个整数数组 nums 和一个正整数 k,请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合. 如果可以,请返回 True:否则,返回 False. 示例 1: 输入:nums = [1,2,3,3,4,4,5,6], k = 4 输出:true 解释:数组可以分成 [1,2,3,4] 和 [3,4,5,6]. 示例 2: 输入:nums = [3,2,1,2,3,4,3

  • C++实现旋转数组的二分查找

    本文实例讲述了C++实现旋转数组的二分查找方法,分享给大家供大家参考.具体方法如下: 题目要求: 旋转数组,如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转,要求利用二分查找查找里面的数. 这是一道很有意思的题目,容易考虑不周全.这里给出如下解决方法: #include <iostream> using namespace std; int sequentialSearch(int *array, int size, int destValue) { int pos

  • Java二分法查找_动力节点Java学院整理

    算法 假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2. 开始令front=0(指向3),end=7(指向88),则mid=3(指向36).因为mid>x,故应在前半段中查找. 令新的end=mid-1=2,而front=0不变,则新的mid=1.此时x>mid,故确定应在后半段中查找. 令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a

  • java实现查找PDF关键字所在页码及其坐标

    1.因为最近有这方面的需求,用过之后记录一下. 2.此功能跟PDF中Ctrl+F性质一样,如果PDF中为图片形式的不支持定位到关键字. import com.itextpdf.awt.geom.Rectangle2D.Float; import com.itextpdf.text.pdf.PdfDictionary; import com.itextpdf.text.pdf.PdfName; import com.itextpdf.text.pdf.PdfReader; import com.i

  • Java实现删除排序数组中重复元素的方法小结【三种方法比较】

    本文实例讲述了Java实现删除排序数组中重复元素的方法.分享给大家供大家参考,具体如下: 题目描述: 给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度. 不要使用额外的数组空间,必须在原地没有额外空间的条件下完成. 一:通过ArrayList解决 时间复杂度和空间复杂度都为O(n) ArrayList<Integer> list = new ArrayList<Integer>(); // 去掉数组中重复的元素 public int r

随机推荐