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.