0%

New Year Chaos

發表於 更新於 分類於

New Year Chaos

規則

  1. 原列隊照順序排，假設有 n 人，那隊伍為[1,2,3,…,n]
  2. 每人個有兩次機會可以跟前面的人交換，假設 1號跟 2號交換，那隊伍為 [2,1,3,…,n]

輸入/輸出

input 為一個亂序陣列

  • 若此陣列不可能有此情況，則輸出 “Too chaotic”
  • 若可交換成此陣列，則輸出 “最小交換次數”

舉例

如果 input 為 [2,1,5,3,4]，輸出最小交換次數 3

如果 input 為 [2,5,1,3,4]，輸出 “Too chaotic”

解答

先替除交換超過 2 次的情形

1
2
3
4
5
6
7
8
9
function line(queue){
    const count = 0
    
    for(let i=1;i< queue.length;i++){
        if(queue[i] - i > 2){
            return 'Too chaotic'
        }  
    }
}

計算交換最小次數

這邊有兩個方法，第一個很直覺，但因為會用到階層，因此函式執行時間會因 length 長度而大量增加

1. 比較所有排比他前面的數字，有大於自己的步數加一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function line(queue){
    let count = 0
    
    for(let i=0; i< queue.length; i++){
        if(queue[i] - (i+1) > 2){
            return 'Too chaotic'
        }
        
        for(let j=0; j<i; j++){
            if(queue[j]> queue[i]){
                count += 1;
            }
        }
    }
    return count;
}

2. 由於每個人不可能跳超過兩步，因此第二個迴圈從 queue[i]-2 算起

假設有個列隊中第 3 個位置是 5號，那這已經是他跳最遠的情況了，此時就沒必較檢查 5 號前面的數字是否大於他，因此檢查起點從他能最遠跳到哪個位置開始算起

那當列隊一長，就會少檢查很多數字，時間複雜度自然會下降

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function line(queue){
    let count = 0
    
    for(let i=0; i< queue.length; i++){
        if(queue[i] - (i+1) > 2){
            return 'Too chaotic'
        }
        
        for(let j= (Math.max((queue[i]-2) || 0)); j<i; j++){
            if(queue[j]> queue[i]){
                count += 1;
            }
        }
    }
    return count;
}