旋转数组
给定一个数组，将数组中的元素向右移动 k个位置，其中 k是非负数。
示例 1:
输入:
[1,2,3,4,5,6,7]和 k = 3
输出:[5,6,7,1,2,3,4]
解释:
向右旋转 1 步:[7,1,2,3,4,5,6]
向右旋转 2 步:[6,7,1,2,3,4,5]向右旋转 3 步:[5,6,7,1,2,3,4]
输入:
[-1,-100,3,99]和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
方法一：暴力
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
for (int i = 0; i < k; i++) {
int temp = nums[n - 1];
for (int j = n - 2; j >= 0; j--) {
nums[j + 1] = nums[j];
}
nums[0] = temp;
}
}
方法二：使用额外空间
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] temp = new int[n];
for (int i = 0; i < n; i++) {
temp[(i + k) % n] = nums[i];
}
for (int i = 0; i < n; i++) {
nums[i] = temp[i];
}
}
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
int[] temp = new int[n];
for (int i = 0; i < k; i++) {
temp[i] = nums[n - k + i];
}
for (int i = k; i < n; i++) {
temp[i] = nums[i - k];
}
System.arraycopy(temp, 0, nums, 0, n);
}
方法三：环状替换
public void rotate(int[] nums, int k) {
int n=nums.length;
int count=0;//记录已替换的个数，做循环出口
for (int i = 0; count < n; i++) {
int pre=nums[i];//保存替换前的值
int index=i;//i表示每轮替换开始的下标，index用来在内存循环中定位应该替换的位置
do{
int newIndex=(index+k)%n;//记录当前的位置，index待会更新为它
int temp=nums[newIndex];//记录当前元素的值，pre待会更新为它
nums[newIndex]=pre;
pre=temp;
index=newIndex;
count++;
} while (index!=i);//形成了一个环，就再从i+1开始
}
}
方法四：三次反转
这个方法基于这个事实：当我们旋转数组 k 次，k%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。
在这个方法中，我们首先将所有元素反转。然后反转前 k 个元素，再反转后面 n-kn−k 个元素，就能得到想要的结果。
假设 n=7 且 k=3
原始数组 : 1 2 3 4 5 6 7
反转所有数字后 : 7 6 5 4 3 2 1
反转前 k 个数字后 : 5 6 7 4 3 2 1
反转后 n-k 个数字后 : 5 6 7 1 2 3 4
public void rotate(int[] nums, int k) {
int n=nums.length;
reverse(nums,0,n-1);
reverse(nums,0,k%n-1);
reverse(nums,k%n,n-1);
}
public void reverse(int[] nums,int start,int end){
while (start<end){
int temp=nums[start];
nums[start]=nums[end];
nums[end]=temp;
start++;
end--;
}
}
寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
旋转数组左边的所有元素都比右边的大
以最后一个元素为参考值num
- 如果nums[mid]<num，说明在右边，缩小右指针范围
- 如果nums[mid]>num，说明在左边，缩小左指针范围
public int findMin(int[] nums) {
return binarySearch(nums,0,nums.length-1);
}
public int binarySearch(int[] nums,int start,int end){
if(start<end){
int mid=(start+end)/2;
if(nums[mid]<nums[end]){//右边
return binarySearch(nums,start,mid);//由于最小元素在右边，所以是mid，不能-1
} else {//左边
return binarySearch(nums,mid+1,end);
}
}
return nums[start];
}
非递归写法
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[right]) {//< 或者<=都行
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];//left或者right都行，因为循环结束时left=right
}
不能用left做参考值的原因：
- 1 2，nums[mid]=nums[l]
- 2 1, nums[mid]=nums[l]
可以改为求最大值，最小值即为最大值后面的一个位置
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (nums[mid] >= nums[l]) {
l = mid;
} else {
r = mid - 1;
}
}
return nums[(l + 1) % nums.length];
}
寻找旋转排序数组中的最小值 II
可能存在重复元素
示例 1：
输入: [1,3,5]
输出: 1
示例 2：
输入: [2,2,2,0,1]
输出: 0
不同之处：可能出现重复元素，出现时right--
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else if (nums[mid] > nums[right]){
left = mid + 1;
} else {
right--;
}
}
return nums[left];
}
不能再采用求最大值后一面一个位置，存在这种情况[3,1,3,3]
搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
数组中不存在重复的元素。
示例 1:
输入: nums = [
4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [
4,5,6,7,0,1,2], target = 3
输出: -1
二分搜索的时候查看当前 mid 为分割位置分割出来的两个部分 [left, mid] 和 [mid + 1, right] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分搜索的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：
- 如果 [left mid - 1] 是有序数组，且 target 在其中，则我们应该将搜索范围缩小至 [left, mid - 1]，否则在 [mid + 1, right] 中寻找。
- 如果 [mid, right] 是有序数组，且 target在其中，则我们应该将搜索范围缩小至 [mid + 1, right]，否则在 [left, mid - 1] 中寻找。
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if(nums[mid]==target){
return mid;
}
if(nums[mid]>=nums[left]){//mid的左边有序
if(target>=nums[left]&&target<nums[mid]){//target在其中
right=mid-1;
}else {
left=mid+1;
}
}else {
if(target>nums[mid]&&target<=nums[right]){
left=mid+1;
} else {
right=mid-1;
}
}
}
return -1;
}
搜索旋转排序数组 II
可能有重复元素
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums =
[2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums =
[2,5,6,0,0,1,2], target = 3
输出: false
10111 和 111011 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
和查找最小数字类似，重复元素导致nums[mid] == nums[left]时，无法判断是左部有序还是右部有序，可以left++，移除重复的元素
public boolean search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] == nums[left]) {
left++;
} else if (nums[mid] > nums[left]) {//mid的左边有序
if (target >= nums[left] && target < nums[mid]) {//target在其中
right = mid - 1;
} else{
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
