刷题记录｜目标101题--排序算法
作者：Hathaway_Z
写在前面
开个贴记录一下 刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～
已刷链接：
- 贪心算法：https://www.nowcoder.com/discuss/1051877
- 双指针：https://www.nowcoder.com/discuss/1057237
- 二分查找：https://www.nowcoder.com/discuss/1059986
排序算法
快速排序
取一个值m，两个指针l与r。
- 先从后向前遍历，如果nums[r]<nums[m],则将nums[m] = nums[r],此时r的位置空出，
- 再从前向后遍历，如果nums[l]>nums[r]，则将nums[r] = nums[l]，此时l的位置空出
- 直至遍历完以后将nums[m]放在最后一个空位，递归左右两边
时间复杂度 & 空间复杂度：
参考链接：https://www.runoob.com/w3cnote/quick-sort.html
并归排序
将一个数组假定为两个，且都已排序过，左右对比插入新的数组
参考链接：https://www.runoob.com/data-structures/merge-sort.html
插入排序
假定前n-1个已经排序好了，把第n个插入到合适的位置
时间复杂度：O(n2) 空间复杂度：O(1)
参考链接：https://www.runoob.com/data-structures/insertion-sort.html
冒泡排序
每次左右对比，把小的放前面，这样最大的就会放到最后
时间负责度：O(n2） 空间复杂度：O（1）
选择排序
十大排序参考：
https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
No. 1 Kth Largest Element in an Array
题目链接：https://leetcode.com/problems/kth-largest-element-in-an-array/
解题思路：
快排的一种变形==》快速选择
class Solution {
public int findKthLargest(int[] nums, int k) {
int l = 0, r = nums.length - 1;
if (l == r) return nums[l];
int target = nums.length - k;
while (l <= r) {
int mid = quickSelection(nums,l,r);
if (mid == target) {
return nums[mid];
} else if (mid > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return nums[l];
}
private int quickSelection(int[] nums,int l, int r) {
if (l == r) return l;
int mid = nums[l];
while (l < r) {
while (r > l && nums[r] >= mid) {
r--;
}
nums[l] = nums[r];
while (l < r && nums[l] <= mid) {
l++;
}
nums[r] = nums[l];
}
nums[l] = mid;
return l;
}
}
No. 2 Top K Frequent Elements
题目链接：
https://leetcode.com/problems/top-k-frequent-elements/
解题思路：
先讲每个数字出现的频率用map记录，key为数字，value为频率，然后将这个map按照频率去排序，排序后从后向前取k个。
这里的map排序使用桶排序，创建一个List<Integer>[] bucket的数组，bucket的下标为频率，将相同频率的放入同一个桶。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums.length == 1) return nums;
Map<Integer,Integer> frequencyMap = new HashMap<Integer,Integer>();
for (int num : nums) {
frequencyMap.put(num,frequencyMap.getOrDefault(num,0) + 1);
}
List<Integer>[] bucket = new List[nums.length + 1];
for (int key : frequencyMap.keySet()) {
int value = frequencyMap.get(key);
if (bucket[value] == null) {
bucket[value] = new ArrayList<>();
}
bucket[value].add(key);
}
ArrayList<Integer> result = new ArrayList<>();
for (int i = bucket.length - 1; i > 0 && result.size() < k;i --) {
if (bucket[i] != null) {
result.addAll(bucket[i]);
}
}
return result.stream().mapToInt(i->i).toArray();
}
}
No.3 Sort Characters By Frequency
题目链接：
https://leetcode.com/problems/sort-characters-by-frequency/
解题思路：
本题与上面一题思路类似，先用map存储字符出现的次数，然后按照次数进行桶排序，最后输出
参考java知识：stringBuilder可以用来改变字符串 https://www.runoob.com/java/java-stringbuffer.html
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> frequency = new HashMap<Character,Integer>();
for (Character c : s.toCharArray()) {
frequency.put(c,frequency.getOrDefault(c,0) + 1);
}
List<Character>[] bucket = new List[s.length() + 1];
for(Character c : frequency.keySet()) {
int value = frequency.get(c);
if (bucket[value] == null) {
bucket[value] = new ArrayList<Character>();
}
bucket[value].add(c);
}
char[] result = new char[s.length()];
for(int i = bucket.length - 1,j = 0; i > 0; i--){
if (bucket[i] != null) {
Character[] chars = bucket[i].toArray(new Character[0]);
for (int q = 0; q < chars.length; q ++){
int fre = i;
while (fre-- > 0) {
result[j++] = chars[q];
}
}
}
}
String out = new String(result);
return out;
}
}
No.4 Sort Colors
题目链接：https://leetcode.com/problems/sort-colors/
解题思路：
如果要在一次遍历和常数的内存中完成，需要用指针存储，分为存储0的指针，存储1的指针和存储2的指针。
遍历的时候：
- 设置代表0的指针a0在最前，代表2的指针a2在最后，代表遍历的指针i
- 如果i!=a0和a2 的时候，是有可能进行交换操作的
- 如果nums[i]== 0,和代表0的指针交换，
- 如果nums[i]==1,则直接走到下一步
- 如果nums[i]==2，则和最后面代表2的指针a2交换
- 等于是前面的0数组从前向后在扩张，后面的2数组从后向前在扩张，中间剩的都就会是1.
class Solution {
public void sortColors(int[] nums) {
int i = 0, k = nums.length - 1;
for(int j = 0; j <= k; j++) {
if (nums[j] == 0 && i != j) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
i++;
j--;
} else if (nums[j] == 2 && j != k) {
int temp = nums[j];
nums[j] = nums[k];
nums[k] = temp;
k--;
j--;
}
}
}
}
#找呀找呀找工作#