about Cyclic sort

Wed, Sep 1, 2021 7-minute read

Cyclic Sort，循环排序

可以用来处理数组中的数值限定在一定的区间的问题。这种模式一个个遍历数组中的元素，如果当前这个数它不在其应该在的位置的话，就把它和它应该在的那个位置上的数交换一下。

这些问题一般设计到排序好的数组，而且数值一般满足于一定的区间 如果问题让你需要在排好序/翻转过的数组中，寻找丢失的/重复的/最小的元素

The idea is simple, if nums[i] != i + 1 and nums[i] != nums[nums[i] - 1], then we swap nums[i] with nums[nums[i] - 1], for example, nums[0] = 4 and nums[3] = 7, then we swap nums[0] with nums[3]. So In the end the array will be sorted and if nums[i] != i + 1, then i + 1 is missing.

这个方法要好好理解下

Missing Number 268

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

 

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

sum 的解法: sums / triangular numbers (n * (n+1) / 2). Someone could get burned in an interview if they were asked “will this approach overflow?” They should be able to answer by reasoning that 10000 * 10001 is safely within the range of 32-bit signed integers, and so no, it will not. Or better yet, at which value of n would it overflow, which we can solve by solving the inequality n(n+1) >= 2^31 (n=46340 is the largest safe value, n=46341 is the smallest value which will overflow).

public int missingNumber(int[] nums) {
        int len = nums.length;
        
        int sum = (len + 0) * (len + 1)/2;
        
        for (int i = 0; i < len; i++) {
            sum -= nums[i];
        }
        return sum;
    }

XOR 的解法 a number XOR itself will become 0, any number XOR with 0 will stay unchanged. So if every number from 1…n XOR with itself except the missing number, the result will be the missing number.

public int missingNumber(int[] nums) {
        int len = nums.length;
        
        for (int i = 0; i < len; i++) {
            res ^= i;
            res ^= nums[i];
        }
        return res;
    }

Find the Duplicate Number 287

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

 

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Time Complexity: O(n) Space Complexity: O(n)

Using a HashSet to record the occurrence of each number.

Time Complexity: O(n) Space Complexity: O(1) Marking visited value within the array Since all values of the array are between [1..n] and the array size is n+1，while scanning the array from left to right, we set the nums[n] to its negative value.

public static int findDuplicate_mark(int[] nums) {
    int len = nums.length;
    for (int num : nums) {
        int idx = Math.abs(num);
        if (nums[idx] < 0) {
            return idx;
        }
        nums[idx] = -nums[idx];
    }
}

Time Complexity: O(n) Space Complexity: O(1)

he key is to understand how to treat the input array as a linked list.

Take the array [1,3,4,2] as an example, the index of this array is [0, 1, 2, 3], we can map the index to the nums[n].

0->1

1->3

2->4

3->2

4->2

 public int findDuplicate(int[] nums) {
       if(nums.length ==0 )
                return 0;
            int slow=0, fast=0;
            slow = nums[slow];
            fast = nums[nums[fast]];
            while(slow != fast){
                if(slow == nums[slow])
                    return slow;
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            fast = 0;
            while(slow != fast){
                if(slow == nums[slow])
                    return slow;
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
    }

Find All Numbers Disappeared in an Array 448

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

[4,3,2,7,8,2,3,1] 4 ！= 1 && 4 ！= nums[3], 4 应该放在索引在 3 的位置 . . [7,3,2,4,8,2,3,1] 4 处理好了， 处理 7, 7 与 3 交换 ; [3,3,2,4,8,2,7,1] 3 应该放在索引在 2 的位置， [2,3,3,4,8,2,7,1] 2 应该在 1 的位置 [3,2,3,4,8,2,7,1] 3 和 索引在 2 的位置的 3 是相等的，跳过， 到了 8 的位置 [3,2,3,4,1,2,7,8] 8 与 1 交换 [1,2,3,4,3,2,7,8] 1 与 3 交换

    public List<Integer> findDisapperdNumbers(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[i];
                nums[i] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                res.add(i + 1);
            }
        }
        return res;
    }

Find All Duplicates in an Array 442

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

我的答案会出界，因为比如 8， 我如果用 index 而不是减 1，要取到 8 就会出界

 nums = [4,3,2,7,8,2,3,1];
 nums[i] = 4;
 index = 4 - 1 = 3;
 nums[3] = 7;
 (7 < 0) = false;
 7 = -7;

 nums = [4,3,2,-7,8,2,3,1];
 nums[i] = 3;
 index = 3 - 1 = 2;
 nums[2] = 2;
 (2 < 0) = false;
 2 = -2;

public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }

First Missing Positive 41

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]
Output: 3

注意空间复杂度，所以不能用 set， set On.

不能建立新的数组，那么只能覆盖原有数组，思路是把 1 放在数组第一个位置 nums[0]，2 放在第二个位置 nums[1]，即需要把 nums[i] 放在 nums[nums[i] - 1]上，遍历整个数组，如果 nums[i] != i + 1, 而 nums[i] 为整数且不大于 n，另外 nums[i] 不等于 nums[nums[i] - 1] 的话，将两者位置调换，如果不满足上述条件直接跳过，最后再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，参见代码如下：

 public int firstMissingPositive(int[] nums) {
        
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                swap(i, nums[i] - 1, nums);
            }
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
    
    private void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
         nums[i] = nums[j];
        nums[j] = tmp;
    }

All Ancestors of a Node in a Directed Acyclic Graph 2192

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

DFS

  • Build graph from parent to kids, and save n empty list into return List ans;
  • Traverse all nodes; for each node, recurse to the lowest offspring;
  • During recursion, add the ancestor into the corresponding ancestors list for each offspring;
  • The recursion terminates once the the ancestor list ends with current ancestor.
 public List<List<Integer>> getAncestors(int n, int[][] edges) {
    List<List<Integer>> ans = new ArrayLisy<>();
    List<List<Integer>> directChild = new ArrayLisy<>(); 

    
    for (int i = 0; i < n; i++) {
        ans.add(new ArrayList<>());
        directChild.add(new ArrayList<>());
    }

    for (int[] e : edges) {
        directChild.add
        dfs(i, i, ans, parentToKids);
    }
    return ans;
}

public void dfs(int ancestor, int kid, int[][] ans, Map<Integer,  List<Integer>> parentToKids) {

    List<Integer> ancestors = ans.get(kid);
    if (ancestors.isEmpty() || ancestors.get(ancestors.size() - 1) != ancestor) {
        if (ancestor != kid) {
            ancestors.add(ancestor);
        }

        for (int grandKid : parentToKids.getOrDefault(kid, Arrays.asList())) {
            dfs(ancestor, grandKid, ans, parentToKids);
        }
    }
}

Time & space: O(n ^ 2 )