937. 重新排列日志文件

937. 重新排列日志文件

leetcode 链接

解法一：二分法排序 + 自定义判断逻辑

1、先遍历数组，分出 字母 和 数字 两种日志。

2、使用二分法排序 字母日志，判断大小的逻辑要根据题目说明来写。

3、合并返回两个数组

/**
 * @param {string[]} logs
 * @return {string[]}
 */
function reorderLogFiles(logs) {
  const digList = []
  const letList = []
  for (const i of logs) {
    if (!isNaN(Number(i.split(' ').splice(1)[0]))) {
      digList.push(i)
    }
    else {
      letList.push({
        originVal: i,
        tag: i.split(' ')[0],
        contentList: i.split(' ').slice(1),
      })
    }
  }
  const letSortList = binary(letList).map(item => item.originVal)
  return letSortList.concat(digList)
}

function binary(list) {
  if (list.length === 0) {
    return []
  }
  else if (list.length === 1) {
    return list
  }
  const left = []
  const right = []
  const flag = list[0].contentList
  for (let i = 1; i < list.length; i++) {
    const conList = list[i].contentList
    if (conList.join(' ') !== flag.join(' ')) {
      let index = 0
      while (true) {
        if (conList[index] < flag[index] || index === conList.length) {
          left.push(list[i])
          break
        }
        else if (conList[index] > flag[index] || index === flag.length) {
          right.push(list[i])
          break
        }
        else {
          index++
        }
      }
    }
    else {
      if (list[i].tag < list[0].tag) {
        left.push(list[i])
      }
      else {
        right.push(list[i])
      }
    }
  }
  return binary(left).concat([list[0]]).concat(binary(right))
}

解法二： sort 方法排序

1、先遍历数组，分出 字母 和 数字 两种日志。

2、使用数组的 sort 方法排序

3、合并返回两个数组

/**
 * @param {string[]} logs
 * @return {string[]}
 */
function reorderLogFiles(logs) {
  const digList = []
  const letList = []
  for (const i of logs) {
    if (!isNaN(Number(i.split(' ').splice(1)[0]))) {
      digList.push(i)
    }
    else {
      letList.push({
        originVal: i,
        tag: i.split(' ')[0],
        content: i.split(' ').slice(1).join(' '),
      })
    }
  }
  const letSortList = letList
    .sort((a, b) => {
      if (a.content !== b.content) {
        return a.content < b.content ? -1 : 1
      }
      else {
        return a.tag < b.tag ? -1 : 1
      }
    })
    .map(item => item.originVal)
  return letSortList.concat(digList)
}

:::info

字符串比较

上面字符串比较我是直接比较大小的，比如 'a' < 'b'，这是允许的，这个表达式的值为 true，因为：

'a'.charCodeAt() // 97
'b'.charCodeAt() // 98

所以非数字字符串比较大小比较的其实是他们 ASCII 码的大小，而且是按顺序比较的，先比较第一位，如果能比较出大小，那结果就是最终结果，如果相等就比较第二位，以此类推。

参考：https://www.fly63.com/article/detial/4071

sort 方法

语法：

arr.sort([compareFunction])

如果没有指明 compareFunction ，那么元素会按照转换为的字符串的诸个字符的 Unicode 位点进行排序。例如 “Banana” 会被排列到 “cherry” 之前。当数字按由小到大排序时，9 出现在 80 之前，但因为（没有指明 compareFunction），比较的数字会先被转换为字符串，所以在 Unicode 顺序上 “80” 要比 “9” 要靠前。

如果指明了 compareFunction ，那么数组会按照调用该函数的返回值排序。即 a 和 b 是两个将要被比较的元素：

• 如果 compareFunction(a, b) 小于 0 ，那么 a 会被排列到 b 之前；
• 如果 compareFunction(a, b) 等于 0 ， a 和 b 的相对位置不变。备注： ECMAScript 标准并不保证这一行为，而且也不是所有浏览器都会遵守（例如 Mozilla 在 2003 年之前的版本）；
• 如果 compareFunction(a, b) 大于 0 ， b 会被排列到 a 之前。
• compareFunction(a, b) 必须总是对相同的输入返回相同的比较结果，否则排序的结果将是不确定的。

以上内容全部从 MDN - Array.prototype.sort() 复制 :::