剑指offer刷题记录-JAVA

剑指offer刷题记录-JAVA

1.数组中重复的数字

Floyd 判圈算法 O(n) O(1)

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int fast = 0;
        int slow = 0;

        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(fast != slow);
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

把数交换到原本的位置，如果已经有数在这个位置了，它就是重复的数 O(n) O(1)

class Solution {
    public int findDuplicate(int[] nums) {
        int i = 0,n = nums.length;
        while(i < n){
            if(i == nums[i]){i++;continue;}//本来就在该在的位置上
            int value = nums[i]; // 要把nums[i] 放value位置
            if(nums[value] == value){return value;}
            //否则交换
            int cor = nums[value];
            nums[value] = nums[i];
            nums[i] = cor;
        }
        return 0;
    }
}