public class MinOfShiftedArray {
/**
* Q69 旋转数组的最小元素
* 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。
* 例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。
*/
public static void main(String[] args) {
int[][] a={
{1,2,3,4,5},
{2,3,4,5,1},
{3,4,5,1,2},
{4,5,1,2,3},
{5,1,2,3,4},
};
for(int[] each:a){
int min=minOfShiftedArray(each);
System.out.println(min);
}
}
/*
* Divide and conquer
*/
public static int minOfShiftedArray(int[] x){
if(x==null||x.length==0){
return -1;
}
int len=x.length;
int low=0;
int high=len-1;
if(x[low]<x[high]){//if the array is not shifted actually,e.g. {1,2,3,4,5}
return x[low];
}
int mid=0;
while(low<high){
mid=(low&high)+(low^high)/2;
if(mid==low){//if there are only two elements left
return x[low]<x[high]?x[low]:x[high];
}
if(x[mid]>x[low]){
low=mid;
}else{
high=mid;
}
}
return x[mid];
}
}
分享到:
相关推荐
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出数组的最小元素。 例如:数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE...
旋转数组的最小数字一把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。例如,数组 [3,4,5,1,2] 为[1,2,3,4,5] 的一个旋转,
题目把一个数组最开始的若干个元素搬到数组的末尾,称之为数组的旋转输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素NOTE:给出的所有元素都大于0,若数
面试题11. 旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5]
题目:把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增数组的旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. 算法: (1)...
js代码-push() 向数组的末尾添加一个或更多元素,并返回新的长度。
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给...
c++1)一个包含10个元素的数组,已按升序排序,输入一个任意的整数, 将该整数插入数组中,使数组元素仍保持升序排列。要求编写一个通用的 插入排序函数InsertSort,它带有三个参数,第一个参数是含有n个元素的数组...
字符串与字符数组 3-1 字符串 存放数值型数据的数组为数值型数组,而字符型数组则是指专门用来存放...数组中每一个元素都是字符型的,称之为字符数组 字符数组的定义:char c[10];或char c[5][10] ; 字符数组的初始化:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小数组。例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的旋转数组,该数组的最小值为1。 思路解析...
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 又例如{...
该代码设计了一个函数用来删除数组中的元素,要求:数组中删除第i个元素,删除的位置用0代替,然后继续在数组中查找第i个元素,(遇到0继续往下找,到达元素末尾后从头查找)
# 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序 # 输入示例 # 输入: [0,1,0,3,12] # 输出示例 # 输出: [1,3,12,0,0] # 解析 # 双指针, 或者冒泡 # 冒泡: 两次循环, ...
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给...
问题描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为...
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出...
- push():向数组末尾添加一个或多个元素,并返回新的长度。 - pop():删除并返回数组的最后一个元素。 - unshift():向数组开头添加一个或多个元素,并返回新的长度。 - shift():删除并返回数组的第一个元素。...
给一个数组,返回它的最大连续子序列的和使用动态规划F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变res:所有子数组的和的
js代码-给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。