javascript - 按字典序排列

Question

所以我试图在 stackoverflow 上解决这个问题

提问链接:https://leetcode.com/problems/reorder-data-in-log-files/

问题:基本上，我们需要对日志重新排序，以便所有字母日志都排在任何数字日志之前。字母日志按字典顺序排列，忽略标识符，在连接的情况下使用标识符。数字日志应按其原始顺序放置。

这个问题我也写过

/**
 * @param {string[]} logs
 * @return {string[]}
 */
var reorderLogFiles = function(logs) {
    const letterLogs = []
    const digitLogs = []
    let i = 0; 
    while (i<logs.length) {
        const logger = logs[i]
        const secondWordIndex = logger.indexOf(' ') + 1 
        console.log(logger[secondWordIndex])
        if (isNaN(logger[secondWordIndex])) letterLogs.push(logger)
        else digitLogs.push(logger)
        i++
    }

    return [...letterLogs, ...digitLogs]
};

但这不是按字典顺序排列的，因为我不确定按字典顺序排列是什么意思

这是给定的输入/输出

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

问题:有人可以帮我制定上述问题的算法吗？我尝试执行 letterLogs.sort((a,b) => a.localeCompare(b)) 但这也不起作用。

Answer 1

维基百科:

In mathematics, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters. This generalization consists primarily in defining a total order over the sequences (often called strings in computer science) of elements of a finite totally ordered set, often called an alphabet.

字典顺序是字母顺序加上长度比较。

也就是说，字符串a在字典序上小于字符串b

• 如果a的长度小于b的长度，或者
• 否则它们的长度相同，并且 a 按字母顺序小于 b。

要按顺序排列项目，必须有一种方法来比较两个项目。对于字符串，通常的顺序是 Lexicographic Order基本上，它是按字母顺序排列的。

lexicographical vs alphabetical-order

你必须根据问题做什么:

在您的问题中，您应该订购所有let*... strings before dig* .... 字符串，在所有 let1* 字符串中，它们应该按字典顺序 与 dig* 字符串相同.

检查以下解决方案:

在数组 logs 中注意，我添加了另一个元素 “let0 art can”，这样应该会出现联系场景。

假设:

1. 所有字符串都将以“let”或“dig”开头。

/*
Basically, we need to Reorder the logs so that all of the letter-logs come before any digit-log. 

The letter-logs are ordered lexicographically ignoring identifiers, 

with the identifier used in case of ties.

The digit-logs should be put in their original order.


*/

let logs = ["dig1 8 1 5 1","let1 art can","let0 art can", "dig2 3 6","let2 own kit dig","let3 art zero"];

//Notice in array logs I have added another element "let0 art can" so that ties scenario should occure.

let letterLogs = logs.filter((log) => log.startsWith("let"));    //get all letter strings 

let digitLogs = logs.filter((log) => log.startsWith("dig"));   //get all digit strings


//custom sort function
let sortFun = function(a, b) {

   let sortResult =  (function removeIdentifiers(a, b){  //remove identifiers
      let aCopy = a.replace(/[0-9]*/gm, "").replace(/\s\s+/gm," ");   //remove digits from the string also replace more than one space with just single space
      let bCopy = b.replace(/[0-9]*/gm, "").replace(/\s\s+/gm," ");;  //remove digits from the string also replace more than one space with just single space
       
      let result = (function sortCopies(a, b){ //sort a and b with identifiers removed
        if(a > b)
          return 1;

        if(b > a)
          return -1;

        return 0;
      })(aCopy, bCopy);

      
      //if identifires removed sort result it 0, i.e. tie the sort with identifiers
      if(result == 0){
         if(a > b)
          return 1;

         if(b > a)
            return -1;

         return 0;
      } else {
        return result;
      }
      
   })(a, b);
   
   return sortResult;  //return the final sort result
   
}

sortedLetterLogs = letterLogs.sort(sortFun)

console.log("sortedLetterLogs", sortedLetterLogs);
/*
sortedLetterLogs [
  "let0 art can",
  "let1 art can",
  "let3 art zero",
  "let2 own kit dig"
]
*/

let finalResult = [...sortedLetterLogs, ...digitLogs ];

console.log("finalResult", finalResult);
/*
finalResult [
  "let0 art can",
  "let1 art can",
  "let3 art zero",
  "let2 own kit dig",
  "dig1 8 1 5 1",
  "dig2 3 6"
]
*/