Sorting – Distinct解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/6-sorting/distinct/

題目解析

這一題之前其實出現過，但是因為這一題A的範圍是負一百萬到正一百萬，實在太大了，沒辦法直接用查表的方式儲存，所以會需要使用到二分搜尋法去建立這個不重複陣列

我的解題記錄

第一次的解法

function solution(A) {
    var M = []
    for (var i = 0; i < A.length; i++) {
        var idx = binarySearch(M, A[i]);
        if(M[idx] != A[i]){
            M.splice(idx, 0, A[i])
        }
    }
    //console.log(M)
    return M.length
}

//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left
}

對於這結果，我真是滿腹委屈，明明二分搜尋法就是O(logN)阿!到底是誰把他變成O(N^2)的…我覺得應該是原本遍歷陣列為N,又乘上搜尋的LogN，因此變得很耗時

經過了一陣思考後，我覺得我根本被這一個章節的篇名所騙了，我幹嘛要建立有序陣列呢?用物件不就好了嗎?甚麼二分搜尋法根本自討苦吃!!

function solution(A) {
    var M = {}
    for (var i = 0; i < A.length; i++) {
        M[A[i]] = true;
    }
    //console.log(Object.keys(M))
    return Object.keys(M).length
}

結果根本沒在鳥甚麼Sorting不Sorting的反而過關，100%PASS!(https://app.codility.com/demo/results/trainingTR8QQS-TDU/)