31. 下一个排列

思路：其实这道题的意思就是，简单地说，就是找到一个比现有的给出的数组代表的值大的最小的数
比如给出的数组是[1,2,3]，它代表的数值是123，现有的元素组成的数值中，比123大的有很多，比如：213，231，312，321……，这些数中最小的一个是132，表示成数组就是[1,3,2]。此集合就是我们要输出的。

解题思路：
1、首先从后先前找，找到第一个满足A[i] < A[j]的位置(i,j)，如果这个位置后面还有元素，那么后面的元素必然是降序排列（j及j之后的元素），说明在后面的元素中，j处的元素是最大的。
为啥要从后往前找第一个升序对，但是因为，每次输出的值都是将数值中尽可能较低位上的元素进行交换，这样得到的就是比现有数值大，但同时又是比现有数值大的元素集合中最小的数。

2、再从后向前找（从数组末尾到j的范围中），找第一个满足A[i] < A[k] 的 k。
因为虽然j出元素比i处的大，但是如果直接交换这两个元素，并不一定保证改动最小，由于j后都是降序，从后向前找到的元素是比i处元素大的最小的一个数，交换他们能够达到目的

3、交换两个元素后，还需要将j及j后的元素变成升序
因为已经将k处和i处交换，减缓后j后元素仍未降序，需要将其改成升序来世得到的值最小

4、如果没有找到这个(i,j)位置，说明整个数组都是降序，代表这个值已经是最大的，根据题意，此时应该将所有元素反转

第一遍错误：

class Solution {public void nextPermutation(int[] nums) {if(nums.length==1) return;int i=nums.length-2;while(i>0&&nums[i]>=nums[i+1]){i--;}if(i>0){int j=nums.length-1;while(j>i&&nums[j]<=nums[i]){j--;}swap(nums,i,j);reverse(nums,i+1,nums.length-1);}else{reverse(nums,i,nums.length-1);}}public void swap(int[] nums,int i,int j){int temp=nums[j];nums[j]=nums[i];nums[i]=temp;}public void reverse(int[] nums,int i,int j){while(i<j){swap(nums,i,j);i++;j--;}}
}

原因：

在这个例子中，i经过while循环，已经在0号位值，而根据代码，i=0时，要将整个数组反转，代码以为i处于0号位置时，整个数组都是降序，直接反转即可，但是这种情况没有考虑。仔细考虑后发现，其实整个数组是降序的表现不应该是i处于0号位置，因为如果i在0处，说明0和1是一对升序。如果i=-1，才能说明整个数组都是降序

改进：

class Solution {public void nextPermutation(int[] nums) {int i=nums.length-2;while(i>=0&&nums[i]>=nums[i+1]){i--;}if(i>=0){int j=nums.length-1;while(j>i&&nums[j]<=nums[i]){j--;}swap(nums,i,j);}reverse(nums,i+1,nums.length-1);}public void swap(int[] nums,int i,int j){int temp=nums[j];nums[j]=nums[i];nums[i]=temp;}public void reverse(int[] nums,int i,int j){while(i<j){swap(nums,i,j);i++;j--;}}
}

33. 搜索旋转排序数组

实话说一开始我感觉这是个弱智题，直接从头遍历，看看target元素在不在不就行了，整的这么花里胡哨。结果一看，要求 O(log n) 的时间复杂度……果然还是我弱智

思路：虽然是旋转，但是从中间分成的两部分中肯定有一部分仍然是有序的，主要看target在哪部分范围内，使用二分查找。

受先判断，mid分开的两个部分，有一部分肯定是有序的，剩下的部分要么全部有序，要么部分有序。
如果是[0,mid)有序：
①先判断target大小，如果在mid左边，将搜索范围缩小至[0,mid)
②否则在[mid,num.length-1]范围寻找
如果是[mid,num.length-1]有序：
同上

代码：

class Solution {public int search(int[] nums, int target) {if(nums.length==1){if(target==nums[0]) return 0;return -1;}int l=0,mid=0,r=nums.length-1;while(l<=r){mid=(l+r)/2;if(nums[mid]==target){return mid;}if(nums[l]<=nums[mid]){//一开始这里没加等号，出错了if(nums[l]<=target&&target<nums[mid]){r=mid-1;}else{l=mid+1;}}else{if(nums[mid]<target&&target<=nums[r]){l=mid+1;}else{r=mid-1;}}}return -1;}
}

首先是在num[l]和nums[mid]这里，比较需要加等号，虽然题目中说了元素没有重复的，但是有可能l和mid指向的是同一个元素，比如[3,1]，target=1