【LeetCode】重新排列句子中的单词

【题目链接】3127. 重新排列句子中的单词

题目描述

「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :

句子的首字母大写 text 中的每个单词都用单个空格分隔。 请你重新排列 text 中的单词，使所有单词按其长度的升序排列。如果两个单词的长度相同，则保留其在原句子中的相对顺序。

请同样按上述格式返回新的句子。

实现思路

1. 将句子按照空格分割为数组
2. 根据每个单词的长度进行升序排序
3. 将第一项的首字母大写
4. 将数组转换为字符串的格式返回

具体代码

方法一

这种是目前想出来最简单的解决方案，直接使用 js 的 sort 方法

这里不同的 JavaScript 引擎实现的方法会有所不同，V8 引擎（Chrome 和 Node.js 使用的引擎）中使用的是 Timsort 算法，是一种稳定的排序算法。

var arrangeWords = function (text) {
  const textArr = text.toLowerCase().split(" ");
  // 直接使用sort方法进行排序
  textArr.sort((a, b) => a.length - b.length);
  textArr[0] = textArr[0][0].toUpperCase() + textArr[0].slice(1);
  return textArr.join(" ");
};

方法二

上面提到了稳定的排序算法，起因是一开始打算使用选择排序，发现不符合题目中“如果两个单词的长度相同，则保留其在原句子中的相对顺序。”的要求。

排序算法分为非稳定排序和稳定排序。

• 非稳定性排序 指在排序过程中，相等元素的相对位置可能会发生改变的排序算法。如果序列中有两个元素相等，经过非稳定排序后，它们的相对顺序可能与排序前不同。常见的非稳定性排序有：
  • 快速排序
  • 选择排序
  • 堆排序
• 稳定性排序指在排序过程中，相等元素的相对位置保持不变的排序算法。如果序列中有两个元素相等，经过稳定排序后，它们的相对顺序与排序前相同。常见的稳定性排序有：
  • 冒泡排序
  • 插入排序
  • 归并排序
  • 计数排序
  • 基数排序
  • 桶排序

使用桶排序

var arrangeWords = function (text) {
  const textArr = text.toLowerCase().split(" ");
  const buckets = {};
  for (const item of textArr) {
    if (buckets[item.length]) {
      buckets[item.length].push(item);
    } else {
      buckets[item.length] = [item];
    }
  }

  let result = [];
  Object.keys(buckets).forEach((keys) => {
    result = result.concat(buckets[keys]);
  });

  result[0] = result[0][0].toUpperCase() + result[0].slice(1);
  return result.join(" ");
};

Array.prototype.sort() - JavaScript | MDN

Getting things sorted in V8 · V8

Timsort - 维基百科，自由的百科全书