Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Daily brush 2021.04.04

• Leetcode: leetcode-cn.com/problems/so…
• Difficulty: Medium
• Method: Bubble sort

The title

• 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.

The sample

• Example 1
Input: [10,2] output: "102"Copy the code
• Example 2
Input: [3,30,34,5,9] output: "3033459"Copy the code

Their thinking

• A sorting algorithm is needed, but the sorting conditions need to be customized
• Key point: customize the sort order
• Analysis:,30,34,5,9 [3]
• take0 s and 1 sSubscript elements, combinations to compare =>330 and 303, if the subscript is1If the number in front of the concatenation is small, you need to subscript it0 s and 1 sThe value exchange of the elements of.
• Because bubble sort is going to happenn - 1Traversal, each time putting the largest to the end of the array.
• aftern - 1After the round, the elements in the array are sorted in a custom order.

expand

• Stability: the position of two equal elements relative to each other in the array changes after sorting
• Do not change: Stable sorting
• Change: Unstable sorting

Bubble sort (whoever is bigger stands on the right)

• Pairs of numbers in the array are compared, moving the largest number to the end of the array each time.
• We need one moreThe variable records whether swapping occurred in this round.
• If no swap has taken place in this round, then the data in the array has been sorted out of the loopbreak
• On the other hand, we’re not done yet
• Time complexity: O (n^2)
• Space complexity: O (1)

swapExchange skills

• Requirement: Complete the exchange of two numbers without using a third intermediate variable
• Plus and minus
• Operation:
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
Copy the code

Quicksort (Classic questions)

• 215. The KTH largest element in an array

ACcode

var minNumber = function(nums) {
// Sort and then splice together
function bubbleSort(arr) {
let alen = arr.length, isChange = false;
for(let i = 0; i < alen; i++) {
if(isChange) break;
isChange = true;
for(let j = 0; j < alen - 1; j++) {
// console.log(arr[j + 1] + ''+ arr[j],arr[j] + '' + arr[j + 1])
if((arr[j + 1] + ' ' +  arr[j]) <= (arr[j] + ' ' + arr[j + 1])){
arr[j + 1] = arr[j + 1] + arr[j];
arr[j] = arr[j + 1] - arr[j];
arr[j + 1] = arr[j + 1] - arr[j];
isChange = false;
}
}
}
}
bubbleSort(nums);
// console.log(nums)
let len = nums.length, ans = ' ';
for(let i = 0; i < len; i++) {
ans += nums[i];
}
return ans;
};
Copy the code

conclusion

• It is not important to use the sorting algorithm, the important point is: the conversion of sorting algorithm conditions.