交換LexOrder聯合發現

所以我正在採訪練習題，我遇到了這個問題：給定一個字符串str和對數組，指示字符串中的哪些索引可以交換，返回從字典中最大的字符串做允許的掉期。您可以交換指數任意次數。交換LexOrder聯合發現

例

對於STR = 「ABDC」和對= [[1，4]，[3，4]]，輸出應該是 swapLexOrder（STR，對）= 「DBCA」。

通過交換給定的索引，您將得到字符串：「cbda」，「cbad」，「dbac」，「dbca」。該列表中詞典上最大的字符串是「dbca」。

我得找到涉及工會工作的答案，但我的回答是太慢：

[time limit] 4000ms (js) 
0 ≤ pairs.length ≤ 5000, 
pairs[i].length = 2. 
1 ≤ str.length ≤ 10^4

有人能幫助我調整我的代碼，以增加它的速度？繼承人的代碼，我有：

function swapLexOrder(str, pairs) { 
    if (!pairs.length){ 
     return str 
    } 

    answerHash = {} 
    unmoved = findUnmoved(pairs, str.length) 
    unionsArr = findUnions(pairs) 


    for (i in unmoved){ 
     answerHash[unmoved[i]] = str[(unmoved[i]-1)] 
    } 

    unionsArr.forEach(function(union){ 
     letters = [] 
     for (i in union){ 
      letters.push(str[(union[i]-1)]) 
     } 

     letters.sort() 
     union.sort(function(a,b){ 
      return b-a 
     }) 

     for (j in union){ 
      answerHash[union[j]] = letters[j] 
     } 
    }) 

    string = [] 
    for (keys in answerHash){ 
     string.push(answerHash[keys]) 
    } 
    return string.join('') 
} 



//if two pairs share a number they belong in the same array 
findUnions = function(pairs, unions){ 
    if (!unions){ 
     unions = [pairs[0]]; 
     pairs.shift(); 
    }else{ 
     if(pairs.length){ 
      unions.push(pairs[0]) 
      pairs.shift() 
     } 
    } 

    if (!pairs.length){ 
     return unions 
    } 

    unite = true 
    while (unite && pairs.length){ 
     unite = false 
     loop1: 
     for (i in unions){ 
      loop2: 
      for (j in pairs){ 
       if (unions[i].includes(pairs[j][0])){ 
        unions[i].push(pairs[j][1]) 
        pairs.splice(j, 1) 
        unite = true 
        break loop1 
       }else if (unions[i].includes(pairs[j][1])){ 
        unions[i].push(pairs[j][0]) 
        pairs.splice(j, 1) 
        unite = true 
        break loop1 
       } 
      } 
     } 
    } 
    return findUnions(pairs, unions) 
} 


findUnmoved = function(pairs, length){ 
    range = [] 
    for (var i=1;i<length+1;i++){ 
     range.push(i); 
    } 
    allNum = [].concat.apply([], pairs) 
    range = range.filter(function(x){ 
     return (!allNum.includes(x)) 
    }) 
    return range 
}

它大概我使用的是找工會，但我想也許我能做到這一點，而無需創建一個哈希函數？另外，如果你們知道解決問題的更好方法，我總是會學習一些新的東西。謝謝！

來源

2017-07-25 Stephen Agwu

這個工作更快。

function swapLexOrder(str, pairs) { 
//Turn pairs into edge lists: O(n+m) 
var graph = new Array(str.length).fill(0).map(e=>[]); 
for(var pair of pairs) { 
    graph[pair[0]-1].push(pair[1]-1); 
    graph[pair[1]-1].push(pair[0]-1); 
} 

//Build all the ccs with dfs: O(n+m) 
var ccs = [], ccnum = 0; 
for(var c in str) { 
    if(ccs[c]) 
     continue; 
    ccs[c] = ++ccnum; 
    var dfs = [...graph[c]]; 
    while(dfs.length) { 
     var d = dfs.shift(); 
     if(ccs[d]) 
      continue; 
     ccs[d] = ccnum; 
     dfs.push(...graph[d]); 
    } 
} 

//Group words by ccs: O(n) 
var ccWords = new Array(ccnum).fill(0).map(e=>[]); 
for(var c in str) { 
    ccWords[ccs[c]-1].push(str[c]); 
} 

//Sort all words: O(n log n) 
ccWords.map(e=>e.sort()); 

//Build the new string: O(n) 
var output = ""; 
for(var c in str) {output += ccWords[ccs[c]-1].pop(); } 
    return output; 
}

來源

2017-09-26 02:13:25

交換LexOrder聯合發現

回答

相關問題