iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
0
Software Development

用JS來刷刷HackerRank系列 第 28

(24)HackerRank-Interview-Arrays-Minimum Swaps 2(javaScript ans)

題目
Minimum Swaps 2
舉例輸入

4
4 3 1 2

舉例輸出

3


舉例輸入

5
2 3 4 1 5

舉例輸出

3


舉例輸入

7
1 3 5 2 4 6 7

舉例輸出

3


解析
這題考最初階的排序
給定從1~n
然後開始排序,計算移共移動幾次位置
那我們先照直覺來
從1開始,如果這個位子不是1
那麼1再哪,對他交換位置
(題目要求這麼做,不能直接去這個數原本的位子)
這次的交換方式是使用位操作
可以應付整數溢出

function minimumSwaps(arr) {
    let i = 0;
    let counter = 0;
    //字串數字化
    let size = arr.length;

    //遍歷所有內容排出從1開始到陣列尾
    for (i = 0; i < size - 1; i++) {
        let correctNum = i + 1;
        //如果這個位子不是
        if (arr[i] !== correctNum) {
            //去找這個位子原本的數現在在哪個index
            let index = arr.indexOf(correctNum)
            // 位子互調
            arr[index] ^= arr[i];
            arr[i] ^= arr[index];
            arr[index] ^= arr[i];
            //交換次數+1
            counter++
        }
    }
    return counter
}

不對呀??怎麼time out了

解析2
因為indexOf是每次都從arr[0]開始遍歷
如果有一萬個元素,每次都從0就會超時
我們一路遍歷下來,已知之前所檢測過的都正確
所以我們必須寫個方法,設定起始index往下找

// Complete the minimumSwaps function below.
function findIndice(arr, correctNum) {
    let iterator = 0
    //從現在主方法遍歷到的index繼續往下遍歷
    while (arr[iterator] !== correctNum) {
        iterator++
    }
    return iterator
}

function minimumSwaps(arr) {
    let i = 0;
    let counter = 0;
    let size = arr.length;
    //遍歷所有內容排出從1開始到陣列尾
    for (i = 0; i < size - 1; i++) {
        //這個位子原本應該的數字
        let correctNum = i + 1;
        //如果這個位子不是
        if (arr[i] !== correctNum) {
            //如果用indexOf每次都會從頭遍歷變會超時
            // let index = arr.indexOf(correctNum)
            //去找這個位子原本的數現在在哪個index
            let index = findIndice(arr, correctNum)
            // 位子互調
            arr[index] ^= arr[i];
            arr[i] ^= arr[index];
            arr[index] ^= arr[i];
            //交換次數+1
            counter++
        }
    }
    return counter
}
 

上一篇
(29)HackerRank-Interview-Dictionaries and Hashmaps-Frequency Queries(javaScript ans)
下一篇
(25)HackerRank-Interview-Arrays-Array Manipulation(javaScript ans)
系列文
用JS來刷刷HackerRank30

1 則留言

0
mingyangshih
iT邦新手 5 級 ‧ 2020-10-13 11:14:01

這個似乎要改成這樣才會過喔

function findIndice(arr, correctNum, i) {
    let iterator = i;
    //從現在主方法遍歷到的index繼續往下遍歷
    while (arr[iterator] !== correctNum) {
        iterator++
    }
    return iterator
}

我要留言

立即登入留言