程序员社区

剑指Offer系列(java版,详细解析)11.旋转数组的最小数字

题目描述

剑指 Offer 11. 旋转数组的最小数字

难度简单

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

示例 1:

输入:[3,4,5,1,2]
输出:1

示例 2:

输入:[2,2,2,0,1]
输出:0

注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

测试用例

  • 功能测试(输入的数组是非递减排序数组的一个旋转,数组中有重复的数字或者没有重复的数字)
  • 边界值测试(输入的数组是一个非递减排序的数组,只包含一个数字的数组)
  • 特殊输入测试(输入空指针)

题目考点

  • 考察应聘者对二分查找的理解。如果遇到从排序的数组中查找数字需要尝试二分查找法。
  • 考察应聘者的沟通能力和学习能力。如果面试官提出新的概念,那么我们可以主动和面试官沟通,多问几个问题,把概念弄清楚。
  • 考察应聘者思维的全面性。排序数组本身是一个数组旋转的一个特例,另外,我们需要考虑到数组中有相同数字的特例。

解题思路

如果遇到从排序的数组中查找数字需要尝试二分查找法。

我们利用两个指针分别指向数组的第一个元素和最后一个元素,我们可以先找到数组中间的元素,如果该中间元素大于或等于第一个元素,则位于前面的非递减子数组,此时我们就可以把第一个指针指向该中间元素,这样就可以缩小寻找的范围,移动以后,第一个指针依然指向前面的非递减数组;否则属于后面的非递减子数组,此时我们就可以把第二个指针指向该中间元素,移动以后,第二个指针依然指向后面的非递减数组。然后循环下去,最终第一个指针将指向前面子数组的最后一个元素,而第二个指针将会指向后面子数组的第一个元素,而第二个指针指向的刚好是最小的元素。循环结束。

参考解题

/** * Author:Viper * Data:2021/3/11 * description: */
public class problem11 {
   
    public int minArray(int[] numbers) {
   
        int len =numbers.length;
        if(len==0)
            return 0;
        int i=0,j=len-1;
        while(i<j){
   
            int mid = i+(j-i)/2;
            if(numbers[mid]<numbers[j])
                j=mid;
            else if(numbers[mid]==numbers[j])
                j--;
            else
                i=mid+1;
        }
        return numbers[i];
    }
}

补充

如果面试题是要求在排序的数组(或者部分排序的数组)中查找一个数字或者统计某个数字出现的次数, 那么我们都可以尝试 二分查找算法

强烈建议在准备面试的时候,一定要对各种排序算法的特点烂熟于胸,能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较他们的优缺点。(特别关注手写快排)

快排算法思想如下:
先在数组中选择一个数字,接下来吧数组中的数字分为两部分,比选择的数字小的数字移到数组的左边,比选择的的数字大的数字移到数组的右边 (善用指针的想法)。然后左右两侧分别递归得到最后结果。

快排算法代码如下:

import java.util.Random;

/** * 快速排序 */
public class QuickSort {
   

    /** * 交换数组中的两个值 * @param array * @param a * @param b */
    public static void swap (int[] array, int a, int b) {
   
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    /** * 分区函数 * 按随机出的基准值分区,将比基准值小放在基准值左边,大的放在基准值右边 * @param data * @param length * @param start * @param end * @return * @throws Exception */
    public static int partition(int data[], int length, int start, int end) throws Exception {
   

        Random random = new Random();

        if (data == null || length <=0 || start <0 || end >= length) {
   
            throw new Exception("Invalid Parameters");
        }

        // 尽量避免极端情况,每次都是以最后一个数字作为基准值,在start和end之间随机出一个数
        int index = start + random.nextInt(end - start + 1);

        // 将比较的值放在数组的最后
        swap(data, index, end);

        // 定义一个指针,指向所有换序之后所有比基准值都小的数据的最右边,最后最指向基准值应该在位置
        int small = start - 1;

        for (int i = start; i < end; i++) {
   
            if (data[i] < data[end]) {
   
                small++;
                // 避免原来就是有序数列的无用交换
                if (small != i) {
   
                    swap(data, small, i);
                }
            }
        }
        // 把基准值放在中间
        small++;
        swap(data, small, end);
        return small;
    }

    /** * 利用分区函数实现快速排序 * 递归 * @param data * @param length * @param start * @param end * @throws Exception */
    public static void quickSort(int[] data, int length, int start, int end) throws Exception {
   
        // 当只剩一个数的时候就不用递归了
        if (start == end) {
   
            return;
        }
        int index = partition(data, length, start, end);
        // 防止异常
        if (index > start) {
   
            quickSort(data, length, start, index - 1);
        }
        if (index < end) {
   
            quickSort(data, length, index + 1, end);
        }

    }
  }

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 剑指Offer系列(java版,详细解析)11.旋转数组的最小数字

一个分享Java & Python知识的社区