算法学习笔记1-分治法

算法

Posted by Cc1over on March 30, 2019

算法学习笔记(一)

引言

笔者是一位大二的学生,网络工程专业没有算法这门课,实属蛋疼,所以笔者跟着其他专业的同学一起去蹭了算法课,然后mark下课堂上老师讲的印象深刻的算法题

归并排序思想找出第K个最小元素

算法框架

1.遍历n个数,把最先遍历到的k个数存入到大小为k的数组中,假设它们即是最小的k个数

2.对这k个数,找到这k个元素中的最大值kmax(找最大值需要遍历这k个数,时间复杂度为O(k))

3.继续遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x,把x与kmax比较:如果x < kmax ,用x替换kmax,并回到第二步重新找出k个元素的数组中最大元素kmax,如果x >= kmax,则继续遍历不更新数组

每次遍历,更新或不更新数组的所用的时间为O(k)或O(0)。故整趟下来,时间复杂度为nO(k)=O(nk)

首先实现一个找到最大值并返回最大值与下标的函数

private static int[] findKMax(int[] arr, int k) {
        int max = arr[0];
        int index = 0;
        for (int i = 1; i < k; i++) {
            if (max < arr[i]) {
                max = arr[i];
                index = i;
            }
        }
        return new int[]{max, index};
 }

然后就用这个函数按照上面的思路实现剩余的逻辑

public static int mergeSortAchieve(int arr[], int k) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr[] is null");
        }
        int length = arr.length;
        int[] elements = new int[k];
        System.arraycopy(arr, 0, elements, 0, k);
        int[] data = findKMax(elements, k);
        int index = data[1];
        int kmax = data[0];
        for (int i = k; i < length; i++) {
            if (arr[i] < kmax) {
                elements[index] = arr[i];
                data = findKMax(elements, k);
                index = data[1];
                kmax = data[0];
            }
        }
        return kmax;
    }

堆排序思想找出第K个最小元素

1.用容量为k的最大堆存储最先遍历到的k个数,同样假设它们是最小的k个数

2.堆中元素是有序的,令k1<k2<…<kmax(kmax设为最大堆中的最大元素)

3.遍历剩余n-k个数,假设每一次遍历到的新的元素的值为x,把x与堆顶元素kmax比较:如果x < kmax,用x替换kmax,然后更新堆(O(logk)),否则不更新堆

样下来,总的时间复杂度:O(k+(n-k)*logk)=O(nlogk)。此方法得益于堆中进行查找和更新的时间复杂度均为:O(logk)(若使用上一种解法:在数组中找出最大元素,时间复杂度:O(k))

public static int heapSortAchieve(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr[] is null");
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) {
            heap.add(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (heap.peek() > arr[i]) {
                heap.poll();
                heap.add(arr[i]);
            }
        }
        return heap.peek();
    }

快速排序思想找出第K个最小元素

算法框架

1.选取S中一个元素作为枢纽元v,将集合S-{v}分割成S1和S2,就像快速排序那样

2.如果k <= S1,那么第k个最小元素必然在S1中

3.如果k = 1 + S1,那么枢纽元素就是第k个最小元素,即找到,直接返回它

4.否则,这第k个最小元素就在S2中,即S2中的第k - S1 - 1个最小元素

先写出快速排序一轮的方法quickOnce

private static int quickOnce(int[] arr, int start, int end) {
        int base = arr[start];
        int s = start, e = end;
        while (s < e) {
            while (s < e && arr[e] > base)
                e--;
            if (s < e) {
                arr[s] = arr[e];
                s++;
            }
            while (s < e && arr[s] < base)
                s++;
            if (s < e) {
                arr[e] = arr[s];
                e--;
            }
        }
        arr[s] = base;
        return s;
    }

然后就是借助上面实现的逻辑完成算法设计

public static int quickSortAchieve(int arr[], int start, int end, int k) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr[] is null");
        }
        int index = quickOnce(arr, 0, arr.length - 1);
        if (index < k) {
            return quickSortAchieve(arr, index + 1, end, k);
        } else if (index > k) {
            return quickSortAchieve(arr, start, index, k);
        } else {
            return arr[index];
        }
    }

线性时间复杂度找出第K个最小元素

实现思想

递归方程T(n)=T(n/c)+O(n)的解仅当1/c<1时为线性,所以争取算法的每一步都在原问题的一个固定的分数部分执行

算法框架

1.将集合S划分为若干个长度为5的子集合

2.对每个子集排序

3.取出各个子集中的中值构成中值序列

4.在中值序列中递归选出中间值,记为x

5.以m为支点对S进行划分,产生S1,S2,S3,其中S1的元素小于x,S2的元素等于x,S3的元素值大于x

6.判断第k个最小元素所在集合,递归的应用以上步骤

// TODO

R与S分别为有r个与s个元素的有序表,s<=r/log r,O(r)合并

实现思想

蛮力法:最简单暴力的做法肯定就是一个一个对比然后添加到结果有序表中,而这里为了优化便是用两个指针,一个指向R,一个指向S,用批量插入到结果有序表中,而时间复杂度就是O(s+r)<=O(r+r/logr)<=O(2r)=O(r)

二分法:上面提及到的蛮力法有一个很多的缺陷就是比较的次数非常多,所以为了去减少这个比较的次数,一种优化的方案就是借用二分查找这种思想去找到插入位置,然后批量插入

蛮力法实现代码如下:

  public static int[] merge(int[] R, int[] S) {
        int length = R.length + S.length;
        int[] result = new int[length];
        // R point
        int i = 0;
        // S point
        int j = 0;
        // result point
        int k = 0;
        while (k != length) {
            if (j == S.length || R[i] < S[j]) {
                result[k++] = R[i++];
            } else if (S[j] < R[i]) {
                result[k++] = S[j++];
            }
        }
        return result;
    }

二分思想代码实现:

首先就是实现一个寻找索引的方法,这个方法借助二分查找的思想实现,找到target元素的目标索引

private static int findIndex(int[] arr, int target, int begin, int end) {
        if (target > arr[end]) {
            return end + 1;
        }
        if (target < arr[begin]) {
            return begin - 1;
        }
        int mid = (end - begin) >>> 1 + begin;
        if (target == arr[mid]) {
            return mid + 1;
        } else if (target < arr[mid]) {
            return findIndex(arr, target, begin, mid - 1);
        } else if (target > arr[mid]) {
            return findIndex(arr, target, mid + 1, end);
        }
        throw new IllegalArgumentException("method findIndex error");
    }

然后就是借助上面这个方法实现合并

public static int[] mergeOptimization(int[] R, int[] S) {
        int length = R.length + S.length;
        int[] result = new int[length];
        // 偏移量
        int offset = 0;
        // 位置量
        int index = 0;
        // R point
        int i = 0;
        // S point
        int j = 0;
        // result point
        int k = 0;
        while (k != result.length) {
            if (j != S.length) {
                index = findIndex(R, S[j], i, R.length - 1);
                offset = index - i;
                if (offset == -1) {
                    result[k++] = S[j++];
                } else {
                    for (int u = 0; u < offset; u++) {
                        result[k++] = R[i++];
                    }
                    result[k++] = S[j++];
                }
            } else {
                result[k++] = R[i++];
            }
        }
        return result;
    }

n长度表,表中有k个有序段,O(nlog k)排序

// TODO