面试算法之螺旋数组查找问题

关注

发布于: 4 小时前

通常我们在面试中遇到有序数组都是长成这样的。

但是考察二分搜索的问题往往不是那么的美好、我们来看一到 leetcode 原题

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

题目的意思是给定一个有序数组,这个有序数组在某一个位置被旋转了。直接看图。本来数组是[0,1,2,3,4,5] 结果数组在 4 出发生了旋转、这样导致 4,5 跑的数组的头部去了，数组变成了[4,5,0,1,2,3,4]。

这样的数组有一个有什么特征呢。

开始是升序突然降到低点然后又开始升序。
有两个升序序列组成

任何数据结构首先将他的图像化。在脑子里有他的数据变化图。

如图所示。所有的螺旋数组问题都是在这种数据组织形式中进行处理。

同行有两种题型。而且都要求在 O(logn 的时间复杂度完成)

在螺旋数组中找到最小的值。
在螺旋数组中找到大于/小于/等于某一个 target 的 fist/last/any 位置的值

我们这里给的题目是要求找到给定 target 的值。首先根据排序数组以及 logn 时间复杂度我们基本可以肯定是用二分法。

二分法的基本步骤就是一个左指针 left、一个右指针 right、在循环内部得到中间节点 mid、然后用 target 和中间节点去比较、从而舍弃一部分肯定不存在解的部分、剩余有解的一部分。这是我们总结的二分法的核心思想。我们只需要根据没到题目具体分析该舍弃那一部分、留下那一部分。

这道题目因为是两个上升序列。所以我们可以将 mid 分别安放在两个上升序列中。左边上升序列和右边上升序列。

如果 mid 在左边上升序列中，并且 target > nums[0] && target < nums[mid] 那么令 right = mid;反之令 left = mid;

如果 mid 在右边上升序列中, 并且 target > nums[mid] 那么令 left = mid ;反之令 right = mid;

public int search(int[] nums, int target) {        int start = 0;        int end   = nums.length - 1;        while (start + 1 < end) {            int mid = start + (end - start) / 2;            if (nums[mid] >= nums[start]) { //如果mid落在左边上升序列中                if (nums[mid] >= target && target >= nums[start]) {                    end = mid;                } else {                    start = mid;                }            }else{//如果mid落在右边上升序列中                if (nums[mid] <= target && target <= nums[end]){                    start = mid;                }else{                    end = mid;                }            }        }        if (nums[start] == target){            return start;        }        if (nums[end] == target){            return end;        }        return -1;    }

复制代码

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
示例 1
输入：nums = [3,4,5,1,2]输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

此题目是要求找到螺旋数组中的最小值。

我们可以将这个题目看作是寻找大于 target 的最小值。也就是大于 4 的最小值。

public int findMin(int[] nums) {        if(nums == null || nums.length == 0){            return -1;        }        //find the first element <= target        int target = nums[nums.length -1];//这里我们令target为nums的最后一个元素。        int left = 0;        int right = nums.length - 1;        while (left + 1 < right){            int mid = left + (right - left) / 2;            if(nums[mid] <= target){                right = mid;            }else {                left = mid;            }        }        if(nums[left] <= target){//由于是求的最小值。所以先比较left的值            return nums[left];        }        return nums[right];    }

复制代码

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0 输出：true

这个题目跟以上题目有一个很明显的区别就是、数组中的元素有可能重复。

 public static boolean search(int[] nums, int target) {        int left  = 0;        int right = nums.length - 1;        while (left + 1 < right) {            int mid = (left + right) / 2;            if (nums[mid] == target) {                return true;            }                      if (nums[mid] == nums[left]) {//① 这里已经确定了mid不是target、那么久缩小区间、left指针往前移动               left++;               continue;           }           if (nums[mid] == nums[right]) {//② 这里已经确定了mid不是target、那么久缩小区间、right指针往后移动               right--;               continue;           }            if (nums[mid] > nums[right]) {                if (target < nums[mid] && target >= nums[left]) {                    right = mid;                } else {                    left = mid;                }            } else {                if (target > nums[mid] && target <= nums[right]) {                    left = mid;                } else {                    right = mid;                }            }        }        if (nums[right] == target) {            return true;        }        if (nums[left] == target) {            return true;        }        return false;    }

复制代码

注意这里的①和②不能写成这样

while (nums[mid] == nums[left]);while (nums[mid] == nums[right]);

复制代码

因为等两个 while 循环结束的时候没有重新计算 mid 的值、下面的比较还根据老的 mid 值去比较确定缩小区间、答案肯定是错误的。

发布于: 4 小时前阅读数: 6

泽睿

关注

还未添加个人签名 2017.12.22 加入

还未添加个人简介

发布

暂无评论

创作场景

面试算法之螺旋数组查找问题

泽睿

评论