排序类
下一个排列
问题描述：整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。必须原地修改，只允许使用额外常数空间。
示例：
1
2输入：nums = [1,2,3]
输出：[1,3,2]思路：
从题目描述我们可以得知，如果要找到下一个排列，可以从以下条件来考虑：
- 从数组的最右边开始，从右往左先确定一个数 i，再从这个数左边开始从右往左找第一个比这个要小的数字 j ,得到一个数对<i, j>。这时，把数字 i, j 位置互换，就可以得到一个新的排列，且这个排列相对于原排列会变大，但这个数对并不一定是最优数对。很显然，数字 i 所在的位置越靠近数组右边，这时的排列在所有的数对对应的新排列中一定是最小的那一个，该数对才是我们要找的最优数对。在两个数字进行对换后，数字 i 原来的位置后面的数字需要进行升序排序。
- 对于一个数组 arr = [3,2,1] 来说，已经找不到比它更大的排列了，此时要置换成[1,2,3]。
由于技术受限，现在自己写的代码还是有点过于冗余了，虽然能通过，但是效率不高，先放这里。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66class Solution {
public void nextPermutation(int[] nums) {
int length = nums.length;
// first, last 用来遍历数组
int last = length-1;
int first = last - 1;
int temp = 0;
// left,right 用来记录最优数对的位置
int left = -1;
int right = -1;
while (last != 0){
first = last-1;
while(first != -1){
if (nums[first] >= nums[last]){
first --;
}else{
if (left < first){
left = first;
right = last;
}
break;
}
}
last --;
}
// 判断是否找到最优数对，如果没有找到则说明没有更大的排列，此时倒置数组即可
if (left!=-1){
temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
// 排序
firstUpQueue(nums, left);
} else{
int i=0;
int j=nums.length-1;
while(i<j){
temp=nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
}
// 对数组first位置后的部分进行升序排列
public void firstUpQueue(int[] nums, int first){
int temp = 0;
for (int i=first+1; i < nums.length-1; i ++){
for (int j=i+1; j < nums.length; j ++){
if (nums[i] > nums[j]){
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
}
}
查找类
搜索旋转排序数组
问题描述：整数数组 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 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例：
1
2输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4思路：
从题目描述，可知我们要使用的算法时间复杂度必须为O(log n)，则我们最先能想到的是使用二分查找算法，其时间复杂度为 O(log n) ，但是题目又告诉我们该数组虽然按升序排列，但是经过旋转操作，如果直接对该数组使用二分查找算法，显然不可行。
我的思路是：找到降序的点，使该数组一分为二，两边都是升序排列，再分别对两边进行二分查找。同时，找降序的点，也需要使用二分查找，这样，总的时间复杂度，算出来还是 O(log n) 。
比如，对于数组nums = [4,5,6,7,0,1,2]，其降序的点在7，0之间，找到后，将数组一分为二，分别使用二分查找找到target。
代码如下，还没有经过优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63class Solution {
public int search(int[] nums, int target) {
int pos=0;
pos = searchChange(nums, 0, nums.length-1);
if (nums.length==1){
if (nums[0] == target){
return 0;
}else{
return -1;
}
}
if (pos==0){
if (nums[0] > nums[1]){
return searchTarget(nums, 0, 0, target) + searchTarget(nums, 1, nums.length, target) + 1;
}else {
return searchTarget(nums, 0,nums.length-1, target);
}
}
return searchTarget(nums, 0, pos, target) + searchTarget(nums, pos+1, nums.length, target) + 1;
}
// 二分查找算法，用于查找目标值
public int searchTarget(int[] nums, int i, int j, int target){
if (i >= j){
if (j < nums.length && nums[j] == target){
return j;
} else {
return -1;
}
} else {
int mid = (i + j) >> 1;
if (nums[mid] == target){
return mid;
}else if(nums[mid] < target){
return searchTarget(nums, mid+1, j, target);
}else {
return searchTarget(nums, i, mid, target);
}
}
}
// 该算法查找数组中降序的点，如nums=[4,5,6,7,0,1,2]，则降序的位置为3.
public int searchChange(int[] nums, int i, int j){
if (i >= j){
if (i+1<nums.length && nums[i] > nums[i+1]){
return i;
} else {
return 0;
}
}else{
int mid = (i + j) >> 1;
if (mid+1 < nums.length && nums[mid] > nums[mid+1]){
return mid;
} else {
return searchChange(nums, i, mid) + searchChange(nums, mid+1, j);
}
}
}
}