算法学习笔记(一)
引言
笔者是一位大二的学生，网络工程专业没有算法这门课，实属蛋疼，所以笔者跟着其他专业的同学一起去蹭了算法课，然后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
