【桶排序】[位运算交换值]40、求最小值

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

​ 输入: [1,2,0]
​ 输出: 3

示例 2:

​ 输入: [3,4,-1,1]
​ 输出: 2
示例 3:

​ 输入: [7,8,9,11,12]
​ 输出: 1
说明:

​ 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

分析：

桶排序方法：比如有num[] = 4213152这一串数字，然后进行遍历

1. 4213152//第0位是4所以第0位和第4-1位换位置
2. 3214152//现在0位是3，和第3-1位换位置
3. 1234152//第0位没问题 第一位没问题，第二位没问题，第三位是1，本来应该和0位换位置，但是0位也是1就不换了，下一个5和第四位换位置
4. 1234512//1和第0位又一样，过，然后 第6位值2和第一位换位置，也是2
5. 遍历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&&currentVal>=1&&currentVal<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];