Java旋转数组的最小数字版
目录
1.题目描述
有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。
示例
输入:[3, 4, 5, 1, 2]
返回值:1
2.题解
分析
题目中的数组为
题目要求我们找出其中的最小值
具体实现
方法一(遍历):
寻找数组中的最小值,遍历数组即可找到最小值
-
public class Solution {
-
public int minNumberInRotateArray(int[] nums) {
-
if(nums.length == 0){
-
return -1;
-
}
-
int min = nums[0];
-
for (int i = 1; i < nums.length; i ) {
-
if (min > nums[i]) {
-
min = nums[i];
-
}
-
}
-
return min;
-
}
-
}
方法二(排序):
使用Arrays.sort方法对数组进行降序排序,则nums[0]即为数组的最小值
-
import java.util.Arrays;
-
-
public class Solution {
-
public int minNumberInRotateArray (int[] nums) {
-
if(nums.length == 0){
-
return -1;
-
}
-
Arrays.sort(nums);
-
return nums[0];
-
}
-
}
方法三(二分查找):
数组原本是一个升序数组,旋转之后,数组被分成两部分,前、后半部分分别为升序,后半部分小于前半部分,我们可以利用二分查找的思想,找到其旋转点,即可找到数组的最小值
首先找到数组首尾两端元素,并求出数组中间的下标
再将数组中间值与数组首尾两端元素进行比较,
若nums[mid] > nums[right],则left = mid 1
若nums[mid] < nums[right],则right = mid
若nums[mid] = nums[right], 则将right向左移动一位,即right--
然后进入下一次循环,循环的条件为left < right
通过不断缩小范围,最终能够找到数组的最小值
完整代码
-
public class Solution {
-
public int minNumberInRotateArray(int[] nums) {
-
if(nums.length == 0){
-
return -1;
-
}
-
int left = 0;
-
int right = nums.length - 1;
-
while(left < right){
-
//找到数组的中点
-
int mid = (left right) / 2;
-
if(nums[mid] > nums[right]){
-
//旋转点在[mid 1, j]中,跳过mid 1左边元素
-
left = mid 1;
-
} else if(nums[mid] < nums[right]){
-
//旋转点在[left, mid]中,跳过mid右边元素
-
right = mid;
-
}else{
-
//缩小right继续查找
-
right--;
-
}
-
}
-
//返回旋转点
-
return nums[left];
-
}
-
}
注:题目出自牛客网,链接如下
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggajgk
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13