Line reference: github.com/chefyuan/al…
Hello, I’m take output blog to urge their brush topic of old, learned ten sorting: in front of the word long | ten basic sorting, once done! , next, let’s see if there is anything that can be sorted on the buckle!
Sorting based
Just a quick look at basic sorting
Basic sort classification:
Basic sorting performance:
| Sorting method | Time complexity (average) | Time complexity (worst) | Time complexity (best) | Spatial complexity | The stability of |
|---|---|---|---|---|---|
| Bubble sort | O (n squared) | O (n squared) | O(n) | O(1) | stable |
| Selection sort | O (n squared) | O (n squared) | O (n squared) | O(1) | unstable |
| Insertion sort | O (n squared) | O (n squared) | O(n) | O(1) | stable |
| Hill sorting | O (n ^ (1.3 -) 2) | O (n squared) | O(n) | O(1) | unstable |
| Merge sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | stable |
| Quick sort | O(nlogn) | O (n squared) | O(nlogn) | O(nlogn) | unstable |
| Heap sort | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | unstable |
| Count sorting | O(n+k) | O(n+k) | O(n+k) | O(n) | stable |
| Bucket sort | O(n+k) | O (n squared) | O(n) | O(n+k) | stable |
| Radix sort | O(n*k) | O(n*k) | O(n*k) | O(n+k) | stable |
More specific can view: word long | ten basic sorting, once done!
Okay, let’s start our happy trip!
Brush the topic field
LeetCode912. Sort arrays
ā Title: 912. Sorting arrays (leetcode-cn.com/problems/so…)
ā Difficulty: medium
š description: given an integer array nums, please arrange the array in ascending order.
Example 1:
Input: nums = [5,2,3,1] output: [1,2,3,5]Copy the codeExample 2:
Nums = [5,1,1,2,0,0] output: [0,0,1,1,2,5]Copy the codeš” ideas:
Arrays. Sort (nums) : The door is over there.
So, without a doubt, we’re going to have to tear it by hand.
If you are not familiar with the sorting algorithm, you can do a bubble sort, but this is obviously only fair, so we choose:
Hand fast row
I’m not going to say much more about quick platoon.
Directly on the code:
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort(int[] nums,int left, int right){
// End condition
if(left>=right){
return;
}
/ / partition
int partitionIndex=partition(nums,left,right);
// Recursive left partition
quickSort(nums,left,partitionIndex-1);
// Recursive right partition
quickSort(nums,partitionIndex+1,right);
}
public int partition(int[] nums,int left,int right){
/ / value
int pivot=nums[left];
//mark marks the subscript
int mark=left;
for(int i=left+1; i<=right; i++){if(nums[i]<pivot){
// If the mark value is less than the base value, mark will move back and switch positions
mark++;
inttemp=nums[mark]; nums[mark]=nums[i]; nums[i]=temp; }}// Put the base value in mark's position
nums[left]=nums[mark];
nums[mark]=pivot;
returnmark; }}Copy the code- š Time complexity: Fast-schedule time complexity O(nlogn)
Have time to sort the ten can be in this exercise on a practice.
LeetCode347. The first K high frequency elements
ā Title: 347. The first K high-frequency elements (leetcode-cn.com/problems/to…)
ā Difficulty: medium
š description:
Given an integer array nums, please sort the array in ascending order.
Example 1:
Input: nums = [1,1,1,2, 3], k = 2 output: [1,2]Copy the codeExample 2:
Input: nums = [1], k = 1Copy the codeTip:
1 <= nums.length <= 105 k is in the range [1, the number of different elements in the array]. The problem data guarantees that the answer is unique. In other words, the set of the first K high-frequency elements in the array is uniqueCopy the code** The time complexity of your algorithm must be better than O(n log n), where n is the size of the array.
š” ideas:
So what’s the first thought in this problem?
Count the occurrence frequency of elements, sort from largest to smallest, and take the first k elements.
We want to challenge the advanced requirements, the time complexity is better than O(nlogn), so the familiar bubble, quick sorting and other comparison classes are not available, can only use the non-comparison class three sorting methods: counting sort, bucket sort, radix sort.
Here we choose HashMap+ bucket sort.
Use HashMap to store the frequency of occurrences of elements, and bucket sort to sort.
The code is as follows:
public int[] topKFrequent(int[] nums, int k) {
// Use HashMap to store the occurrence frequency of elements
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
/ / barrel
List<Integer>[] buckets = new List[nums.length + 1];
// Add the number of occurrences to the bucket
for (Integer key : map.keySet()) {
// Determine which bucket the element goes into based on the occurrence frequency
int count = map.get(key);
// Initialize the bucket
if (buckets[count] == null) buckets[count] = new ArrayList<>();
// Store the element in the bucket
buckets[count].add(key);
}
// Result list
List<Integer> result = new ArrayList<>();
// Take the reciprocal of k non-empty buckets
for (int i = buckets.length - 1; k > 0; i--) {
if(buckets[i] ! =null) {
// Take the elements out of the bucket
for(Integer num : buckets[i]) { result.add(num); k--; }}}// Assign the elements of the list to the array
int[] res = new int[result.size()];
for (int i = 0; i < res.length; i++) {
res[i] = result.get(i);
}
return res;
}
Copy the code- š Time complexity: this problem uses bucket sorting, time complexity O(n).
Offer 45. Arrange the array to the smallest number
45. Arrange the array to the smallest number (leetcode-cn.com/problems/ba…)
ā Difficulty: medium
š description:
Enter an array of non-negative integers, concatenate all the numbers in the array into a number, and print the smallest number that can be concatenated.
Example 1:
Input: [10,2] output: "102"Copy the codeExample 2:
Input: [3,30,34,5,9] output: "3033459"Copy the codeš” ideas:
A little bit of analysis of this problem, it turns out that this problem is also a sorting problem.
As long as we sort the elements of the array by some sort of rule.
Now the question is what is this ordering rule?
Since we need to concatenate strings, for example [3, 30], “3” +” 30 “=” 330 “, “30 “+”3″=”303”, 330>303, then we can say that 3 is greater than 30.
So define the rules:
- If the concatenation string x+y>y+x, then x
Is greater thanY; - Otherwise, if the concatenation string x+y<y+x, then x
Less thanY;
The rule diagram is as follows (source reference [2] :
So, we know how to write this problem.
Sort the array from smallest to largest using our custom sorting rules.
We chose quicksort, so this is a custom sort + quicksort.
The code is as follows:
public String minNumber(int[] nums) {
quickSort(nums, 0, nums.length - 1);
/ / the result
StringBuilder sb = new StringBuilder();
for (int num : nums) {
sb.append(String.valueOf(num));
}
return sb.toString();
}
/ / fast row
public void quickSort(int[] nums, int left, int right) {
if (left >= right) return;
int partionIndex = partion(nums, left, right);
quickSort(nums, left, partionIndex - 1);
quickSort(nums, partionIndex + 1, right);
}
public int partion(int[] nums, int left, int right) {
int pivot = nums[left];
int mark = left;
for (int i = left + 1; i <= right; i++) {
if (lessThan(nums[i], pivot)) {
mark++;
int temp = nums[mark];
nums[mark] = nums[i];
nums[i] = temp;
}
}
nums[left] = nums[mark];
nums[mark] = pivot;
return mark;
}
// Customize size comparison rules
public boolean lessThan(int x, int y) {
String sx = String.valueOf(x), sy = String.valueOf(y);
return (sx + sy).compareTo(sy + sx) < 0;
}
Copy the codeIt’s bloated, but it’s clear.
There is a way to use built-in sort, which is not recommended:
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++){
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, (x,y) -> (x+y).compareTo(y+x));
StringBuilder ans = new StringBuilder();
for(String s : strs)
ans.append(s);
return ans.toString();
}
Copy the code- š Time complexity: O(nlogn).
179. The maximum number is basically the same as this problem.
Sword refers to Offer 51. Reverse pair in array
ā title: Sword pointer Offer 51. Array of inversions (leetcode-cn.com/problems/sh…)
ā Difficulty: Difficult
š description:
Two digits in an array form a reverse pair if the preceding digit is larger than the following digit. Enter an array and find the total number of inversions in the array.
Example 1:
Input: [7,5,6,4] output: 5Copy the codeš” ideas:
This problem is difficult, have you been scared?
In fact, this problem if you use merge sort to solve the idea, it is not as difficult as imagined.
I’m not going to talk about merge sort.
To solve this problem, we just need to add the statistics of inversions to merge sort:
Statistical diagram of merge + reverse pair (picture source reference [3]) :
Now the key point is, how do you count inversions when you merge?
Num [l]>nums[r], num[l]>nums[r], num[l]>nums[r], num[l]>nums[r], num[l]>nums[r].
The code is as follows:
class Solution {
// The statistics are in reverse order
int count = 0;
public int reversePairs(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return count;
}
// merge sort
public void mergeSort(int[] nums, int left, int right) {
/ / end
if (left >= right) return;
int mid = left + (right - left) / 2;
// Left half
mergeSort(nums, left, mid);
// Right half
mergeSort(nums, mid + 1, right);
/ / merge
merge(nums, left, mid, right);
}
/ / merge
public void merge(int[] arr, int left, int mid, int right) {
// Temporary array
int[] tempArr = new int[right - left + 1];
// Pointer to left and right subarrays
int l = left, r = mid + 1;
int index = 0;
// Add the smaller elements of the left and right subarrays to the temporary array
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
tempArr[index++] = arr[l++];
} else {
// Add a row, statistical reverse pair
count += (mid - l + 1); tempArr[index++] = arr[r++]; }}// Copy the remaining elements of the left subarray into the temporary array
while (l <= mid) {
tempArr[index++] = arr[l++];
}
// Copy the remaining elements of the right subarray into the temporary array
while (r <= right) {
tempArr[index++] = arr[r++];
}
// Copy the elements of the temporary array to the original array
for (int i = 0; i < tempArr.length; i++) { arr[i + left] = tempArr[i]; }}}Copy the code- š Time complexity: merge sort time complexity O(nlogn).
LeetCode147. Insert sort on linked lists
ā title: Sword pointer Offer 51. Array of inversions (leetcode-cn.com/problems/sh…)
ā Difficulty: Difficult
š description:
Insert sort the linked list.
Insert the sort of animation shown above. Starting with the first element, the list can be considered partially sorted (shown in black). At each iteration, an element (shown in red) is removed from the input data and inserted in place into the sorted linked list.
Insert sort algorithm:
- Insertion sort is iterative, moving one element at a time until all the elements can form an ordered output list.
- In each iteration, insert sort removes only one element to be sorted from the input data, finds its proper place in the sequence, and inserts it.
- Repeat until all input data has been inserted.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4Copy the codeExample 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5Copy the codeš” ideas:
This problem is not only insertion sort, but also related to the operation of linked lists. About linked lists, you can see: LeetCode: I heard that linked lists are the threshold, so I took the foot to enter the door
- About insertion sort: We need to insert elements in the unsorted sequence into the appropriate positions in the sorted sequence
- About linked list insertion: Linked list insertion is an operation that inserts nodes before and after nodes. In order to unify the head insertion, we usually add a virtual head node
- Therefore, to sum up, we need to mark the boundary point of ordered sequence and unordered sequence, record the precursor when traversing the unordered sequence, traverse the ordered sequence when inserting the unordered sequence into the ordered sequence, find the insertion position, delete the node first, and then insert
The code is as follows:
public ListNode insertionSortList(ListNode head) {
if (head == null && head.next == null) {
return head;
}
// Virtual head node
ListNode dummy = new ListNode(-1);
dummy.next = head;
// Record the end of the ordered sequence
ListNode last = head;
// Iterate over an unordered sequence
ListNode after = head.next;
while(after ! =null) {
if (last.val <= after.val) {
after = after.next;
last = last.next;
continue;
}
// Iterate through the ordered sequence to find the insertion position
ListNode prev = dummy;
while (prev.next.val <= after.val) {
prev = prev.next;
}
// Find the insertion position
// Delete the unordered sequence node
last.next = after.next;
// Insert the ordered sequence
after.next = prev.next;
prev.next = after;
// Continue moving
after=last.next;
}
return dummy.next;
}
Copy the code- š Time complexity: O(nĀ²).
conclusion
A familiar catchphrase summary:
Do simple things repeatedly, do repetitive things carefully, and do serious things creatively.
I am three points evil, a pursuit of strength, is working hard programmer.
Like, pay attention to not get lost, let’s see you next time!
Reference:
[1]. Github.com/chefyuan/al… [2]. Leetcode-cn.com/problems/ba… [3]. Leetcode-cn.com/problems/sh…