【桶排序】[位运算交换值]40、求最小值
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3: 输入: [7,8,9,11,12]
输出: 1
说明: 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
分析：
桶排序方法：比如有num[] = 4213152这一串数字，然后进行遍历
- 4213152//第0位是4所以第0位和第4-1位换位置
- 3214152//现在0位是3，和第3-1位换位置
- 1234152//第0位没问题 第一位没问题，第二位没问题，第三位是1，本来应该和0位换位置，但是0位也是1就不换了，下一个5和第四位换位置
- 1234512//1和第0位又一样，过，然后 第6位值2和第一位换位置，也是2
- 遍历num比较下标i和值val 是否符合i=val-1找到第一个不符合的，然后返回
public int firstMissingPositive(int[] nums) {
// 第一步，对需要进行调整的数据进行整理
for (int i = 0; i < nums.length; i++) {
//
int currentVal = nums[i];
System.out.println(i+"======"+currentVal);
if(currentVal!=i+1&¤tVal>=1&¤tVal<nums.length&&nums[currentVal-1]!=currentVal) {
//这个时候如何处理将i位置的数字放至标准呢为止
switchPlace(nums,i,currentVal-1);
i--;
}
}
System.out.println(nums);
//第二部，找到第一个数字
for (int i = 0; i < nums.length; i++) {
//
int currentVal = nums[i];
if(i+1!=currentVal) {
//这个时候如何处理将i位置的数字放至标准呢为止
return i+1;
}
}
return nums.length+1;
}
private void switchPlace(int[] nums, int i, int j) {
// TODO Auto-generated method stub
System.out.println("i"+i+"j"+j);
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
另外位运算交换值：
nums[i] = nums[i]^nums[j];
nums[j] = nums[j]^nums[i];
nums[i] = nums[j]^nums[i];
