代码之家 › 专栏 › 技术社区 › hackrack

在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

time-complexity algorithm javascript

hackrack · 技术社区 · 6 年前

我试图解决一个时间复杂度较低的问题,在这种情况下 O(n) 。

问题是:

let arr = ['dog', 'come', 'ogd', 'something', 'emoc'];

它应该会回来

[['dog', 'ogd], ['come', 'emoc']]; // which same using letters

到目前为止,我用两个函数解决了这个问题,它工作得很好,但我的是嵌套循环 O(n2)

这是我的密码

const isSameChars = (str1, str2) => {
  let str1sorted = str1.split("").sort().join("");
  let str2sorted = str2.split("").sort().join("");
  if (str1.length !== str2.length) {
    return false;
  }
  for (var i = 0; i < str1sorted.length; i++) {
    let char1 = str1sorted[i];
    let char2 = str2sorted[i];
    if (char1 !== char2) {
      return false;
    }
  }
  return true;
}

const isSameCharElements = (arr) => {
  let result = [];
  for(var i = 0; i < arr.length; i++) {
    for(var j = 0; j < i; j++) {
      if (isSameChars(arr[i], arr[j]) === true) {
        result.push(arr[j])
      }
    }
  }
  return result; 
}

console.log(isSameCharElements(['dog', 'come', 'ogd', 'something', 
'emoc'])) //  [['dog', 'ogd], ['come', 'emoc']]

有没有办法解决这个问题 O(n) 时间复杂性?

谢谢你的预付款!

1 回复 | 直到 6 年前

Valentin Waeselynck 6 年前

通过对字母进行排序,可以获得任意字符串的“字母袋”表示:

function sortLetters(word){
  return word.split('').sort().join('');
}

然后可以迭代输入,将具有相同字母袋表示的单词分组到一个对象中:

const grouped = arr.reduce(function (m, word) {
  var bagRepr = sortLetters(word);
  var withSameLetters =  m[bagRepr] ||Â [];
  withSameLetters.push(word);
  m[bagRepr] = withSameLetters;
  return m;
}, {});

const result = Object.values(grouped)
  .filter(function (arr) {
    return arr.length > 1;  
  });

这是O(n),前提是 sortLetters() 是O(1),如果单词长度以常数为界,则为O(1)。

免责声明: 请注意,我们这里只讨论渐近复杂性-这并不意味着从实际角度来看,这种方法是最有效的!

推荐文章

hackrack · 在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

6 年前

data-oil · 在字符串列表中搜索的高效快捷方法

6 年前

user8514739 · 该算法查找长度为X的所有有序排列的算法复杂性

6 年前

Monk · 为什么大Oh不总是算法的最坏情况分析?

6 年前

Qasim Idrees · 三个嵌套相关循环的算法时间复杂度分析

6 年前

sdweldon · O(n)vs O(nlogn)时间复杂度

6 年前

Dazcii · 如何找到3个嵌套循环的复杂性

6 年前

Kodean · Java:循环字符串长度时间复杂性

6 年前

Hal · 循环的时间复杂度是多少?

6 年前

J. Doe · 按O(n)排序的列表中的数字平方?

6 年前