題目內容
題目頁面: 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/)
