NC Note: BFS Template and Topological Sorting

无需分层遍历的宽度优先搜索

// T 指代任何你希望存储的类型
Queue<T> queue = new LinkedList<>();
Set<T> set = new HashSet<>();

set.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
    T head = queue.poll();
    for (T neighbor : head.neighbors) {
        if (!set.contains(neighbor)) {
            set.add(neighbor);
            queue.offer(neighbor);
        }
    }
}

需要分层遍历的宽度搜先搜索

// T 指代任何你希望存储的类型
Queue<T> queue = new LinkedList<>();
Set<T> set = new HashSet<>();

set.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        T head = queue.poll();
        for (T neighbor : head.neighbors) {
            if (!set.contains(neighbor)) {
                set.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

前一节后一节

• set/seen 与 queue 是一对好基友，无时无刻都一起出现，往 queue 里新增一个节点，就要同时丢到 set 里。

Topological sorting
定义

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。

• 每个顶点出现且只出现一次；
• 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

(来自 Wiki)

实际运用

拓扑排序 Topological Sorting 是一个经典的图论问题。他实际的运用中，拓扑排序可以做如下的一些事情：

• 检测编译时的循环依赖
• 制定有依赖关系的任务的执行顺序

拓扑排序不是一种排序算法

虽然名字里有 Sorting，但是相比起我们熟知的 Bubble Sort, Quick Sort 等算法，Topological Sorting 并不是一种严格意义上的 Sorting Algorithm。

确切的说，一张图的拓扑序列可以有很多个，也可能没有。拓扑排序只需要找到其中一个序列，无需找到所有序列。

拓扑排序的算法是典型的宽度优先搜索算法，其大致流程如下：

1. 统计所有点的入度，并初始化拓扑序列为空。
2. 将所有入度为 0 的点，也就是那些没有任何依赖的点，放到宽度优先搜索的队列中
3. 将队列中的点一个一个的释放出来，放到拓扑序列中，每次释放出某个点 A 的时候，就访问 A 的相邻点（所有A指向的点），并把这些点的入度减去 1。
4. 如果发现某个点的入度被减去 1 之后变成了 0，则放入队列中。
5. 直到队列为空时，算法结束，

NC Note: Quick sort, merge sort and quick select

1. Quick Sort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        
        int left = start, right = end;
        // key point 1: pivot is the value, not the index
        int pivot = A[(start + end) / 2];

        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left++;
            }
            
            while (left <= right && A[right] > pivot) {
                right--;
            }
            
            if (left <= right) {
                swap(A, left, right);
                left++;
                right--;
            }
        }
        
        quickSort(A, start, right);
        quickSort(A, left, end);
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

2. Merge Sort

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortIntegers2(int[] A) {
        if (A == null || A.length < 2) {
            return;
        }

        int[] temp = new int[A.length];

        sortIntegers2Helper(A, temp, 0, A.length - 1);
    }

    private void sortIntegers2Helper(int[] A, int[] temp, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;
        sortIntegers2Helper(A, temp, start, mid);
        sortIntegers2Helper(A, temp, mid + 1, end);

        // merge
        //
        merge(A, temp, start, end);
    }

    private void merge(int[] A, int[] temp, int start, int end) {
        int mid = start + (end - start) / 2;
        int i = start;
        int j = mid + 1;
        int k = start;

        while (i <= mid || j <= end) {
            if (i > mid) {
                temp[k++] = A[j++];
            } else if (j > end) {
                temp[k++] = A[i++];
            } else if (A[i] < A[j]) {
                temp[k++] = A[i++];
            } else {
                temp[k++] = A[j++];
            }
        }

        for (i = start; i <= end; i++) {
            A[i] = temp[i];
        }
    }
}

3. Quick Select

public class Solution {
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        return kthLargestElementHelper(nums, 0, nums.length - 1, nums.length - n);
    }
    
    private int kthLargestElementHelper(int[] nums, int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
        
        int i = start;
        int j = end;
        int pivot = nums[(i + j) / 2];
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] > pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
        
        if (k <= j) {
            return kthLargestElementHelper(nums, start, j, k);
        } else if (k >= i) {
            return kthLargestElementHelper(nums, i, end, k);
        } else {
            return nums[k];
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Another version:

public class Solution {
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0 || n > nums.length) {
            return -1;
        }

        return kthLargestElementHelper(nums, 0, nums.length - 1, n);
    }

    private int kthLargestElementHelper(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }

        int i = start;
        int j = end;

        int pivot = nums[(i + j) / 2];

        while (i <= j) {
            while (i <= j && nums[i] > pivot) {
                i++;
            }

            while (i <=j && nums[j] < pivot) {
                j--;
            }

            if (i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;

                i++;
                j--;
            }
        }

        if (j - start + 1 >= k) {
            return kthLargestElementHelper(nums, start, j, k);
        }

        if (i - start + 1 <= k) {
            return kthLargestElementHelper(nums, i, end, k - i + start);
        }

        return nums[j + 1];
    }
}

Another version:

public class Solution {
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
        return kthLargestElementHelper(nums, 0, nums.length - 1, nums.length - n + 1);
    }
    
    private int kthLargestElementHelper(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }
        
        int i = start;
        int j = end;
        int pivot = nums[(i + j) / 2];
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] > pivot) {
                j--;
            }
            
            if (i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                
                i++;
                j--;
            }
        }
        
        if (j - start + 1 >= k) {
            return kthLargestElementHelper(nums, start, j, k);
        }
        
        if (i - start + 1 <= k) {
            return kthLargestElementHelper(nums, i, end, k - i + start);
        }
        
        return nums[j + 1];
    }
}

NC Note:Time complexity

Chapter 2: Binary Search

1. Binary search time complexity:

T(n) = T(n/2) + O(1)
     = T(n/4) + O(1) + O(1)
     = T(n/8) + O(1) * 3
     = T(n/16) + O(1) * 4
     ...
     = T(1) + O(1) * logn 

     = O(logn) 

2. T(n)=T(n/2)+O(n)

T(n) = T(n/2) + O(n)
     = T(n/4) + O(n/2) + O(n)
     = T(n/8) + O(n/4) + O(n/2) + O(n)
     = ...
     = O(1) + O(2) + ... O(n/2) + O(n)
     = O(1 + 2 + 4 .. + n/2 + n)
     = O(2n) = O(n)

许多同学会拍脑袋认为这个式子的结果是 O(nlogn)，这是错误的。主要错在，当 T(n/2) 往下继续展开的时候，很多同学直接写成 T(n/4) + O(n)，这是不对的。应该是 T(n/4) + O(n/2)。这里我们暂时不能约掉 O(n/2) 里的 /2。因为会导致误差累积。

另外一个需要记住的结论就是：O(1 + 2 + 4 ... + n/2 + n) = O(n)。 geometric sequence sum Sn = a1 * (1 - q^n) / (1 - q)

3. Merge sort

T(n) = 2 * T(n / 2) + O(n)

T(n) = 2 * T(n/2) + O(n)
     = 2 * (2 * T(n/4) + O(n/2)) + O(n)
     = 4 * T(n/4) + 2 * O(n/2) + O(n)
     = 4 * T(n/4) + 2 * O(n)
     = 4 * (2 * T(n/8) + O(n/4)) + 2 * O(n)
     = 8 * T(n/8) + 3 * O(n)
     = 16 * T(n/16) + 4 * O(n)
     ...
     = n * T(1) + logn * O(n)
     = O(n) + O(nlogn)
     = O(nlogn)

4. T(n)=2∗T(n/2)+O(1)

T(n) = 2 * T(n/2) + O(1)
     = 2 * (2 * T(n/4) + O(1)) + O(1)
     = 4 * T(n/4) + O(2 + 1)
     = 8 * T(n/8) + O(4 + 2 + 1)
     ...
     = n * T(1) + O(n/2 + n/4 + ... + 2 + 1)
     = O(n) + O(n)
     = O(n)

 4. int Fibo(int n) {

    if (n == 0 || n == 1) return 1;
    return Fibo(n - 1) + Fibo(n - 2);
}

时间复杂度为 $O(2^\frac{n}{2})$ ~ $O(2^n)$

计算时间复杂度上界：$Fibo(n) = Fibo(n-1) + Fibo(n-2) < 2 * Fibo(n-1)$
也就是说，递归版 Fibonacci 的时间复杂度 < $T(n) = 2 * T(n-1) + O(1) = O(2^n)$

再来计算时间复杂度下界：$Fibo(n) = Fibo(n-1) + Fibo(n-2) > 2 * Fibo(n-2)$
也就是说，递归版 Fibonacci 的时间复杂度 > $T(n) = 2 * T(n-2) + O(1) = O(2^\frac{n}{2})$