Maximum Swap

Description

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973
Output: 9973
Explanation: No swap.

Note:

1. The given number is in the range [0, 10⁸]

Solution(javascript)

/** 转成字符串，排序， 比对对应的位置是不是一样
 * @param {number} num
 * @return {number}
 */
// const maximumSwap = function (num) {
//   const str = num.toString()
//   const sorted = str.split('').sort((a, b) => b.localeCompare(a))
//   const findFromRight = (c) => {
//     for (let i = str.length - 1; i >= 0; i--) {
//       if (str[i] === c) {
//         return i
//       }
//     }
//     return -1
//   }
//   for (let i = 0; i < sorted.length; i++) {
//     if (sorted[i] !== str[i]) {
//       const index = findFromRight(sorted[i])
//       const arr = str.split('')
//       const temp = arr[i]
//       arr[i] = arr[index]
//       arr[index] = temp
//       return parseInt(arr.join(''), 10)
//     }
//   }
//   return num
// }

// O(n) 记录每个数字最后出现的位置
const maximumSwap = function (num) {
  const str = num.toString().split('')
  const positions = str.reduce((acc, v, i) => {
    acc[v] = i
    return acc
  }, [])
  for (let i = 0; i < str.length; i++) {
    for (let j = positions.length - 1; j - str[i] > 0; j--) {
      if (positions[j] > i) {
        const index = positions[j]
        const temp = str[i]
        str[i] = str[index]
        str[index] = temp
        return parseInt(str.join(''), 10)
      }
    }
  }
  return num
}