Sorting – NumberOfDiscIntersections解題紀錄

題目內容

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

解題思考

這個是在算N個圓是否有交集，例如以題目來說，A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0單純以範圍來看，會是這樣的範圍陣列[ -1, 1 ], [ -4, 6 ], [ 0, 4 ], [ 2, 4 ], [ 0, 8 ], [ 5, 5 ]，要尋找在這些範圍內取出兩者是有交集的

先用C6取2算出兩兩相配的最多次數，然後找出沒有交集的圈圈，就會是(0,3),(0,5),(2,5),(3,5)沒有交集，我們使用C6取2減掉沒有交集的4個，就會是有交集的數字11

解題紀錄

先用暴力法把沒有交集的找出來

function solution(A) {
    var count = A.length*(A.length-1)/2;
    for(var i=0;i<A.length;i++){
        for(var j = i+1;j<A.length;j++){
            if(i+A[i] < j-A[j]){
                count--;
            }
        }
    }
    return count
}

好，至少答案是正確的，先來想想優化方式

嘗試換個寫法，儲存所有結束的點(照順序排序)，然後後面的用開始的點去比較之前的結束的點，看看會不會比前面結束的點更大，若更大代表沒有交集，這樣子做會可以在計算時透過排序去節省時間。

function solution(A) {
    var range = []
    var no_intersect = 0
    for(var i=0;i<A.length;i++){
        var count = binarySearch(range, i-A[i])
        no_intersect += count
        //console.log(range,count, i-A[i])
        range.splice(binarySearch(range, i+A[i]), 0, i+A[i])
    }
    return A.length*(A.length-1)/2 - no_intersect
}
//在一個已排序的陣列裡，取得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
}

應該有邊界性的邏輯錯誤QQ但效能是有一個有通過了，來找找邊界性錯誤的位置…

哈..發現問題了

The function should return −1 if the number of intersecting pairs exceeds 10,000,000

所以就是用第一次的寫法，然後若數字超過直接就返回錯誤。但是因為這樣要知道現在的次數，所以要改一下加總的方式

function solution(A) {
    var count = 0//A.length*(A.length-1)/2;
    for(var i = A.length-1;i >=0;i--){
        for(var j = i-1;j>=0;j--){
            if(i-A[i]<=j+A[j]){
        //console.log(i,j)
                count++
                if(count > 10000000) return -1
            }
        }
    }
    return count
}

原來即便是跑到10000000就return也是超過標準…

經過思考之後，我覺得還是去尋找我第二個做法邏輯錯誤的部分好了…

我覺得應該是我在實作二分搜尋法上面的問題，因為對這個題目而言，應該要尋找”第一個”<=目標值的index，但是因為現在使用的二分搜尋法的邏輯，很可能所選到的不會是第一個，這樣就會造成些微的錯誤，所以會需要在遇到第一個arr[mid] === target的時候，往前搜尋確認現在的mid是第一個大於等於目標值的index

function solution(A) {
    var range = []
    var total = A.length*(A.length-1)/2
    var no_intersect = 0
    for(var i=0;i<A.length;i++){
        var count = binarySearch(range, i-A[i])
        no_intersect += count
        //console.log(range,count, i-A[i])
        range.splice(binarySearch(range, i+A[i]), 0, i+A[i])
        
    }
    var intersecting = total - no_intersect
    return intersecting > 10000000 ? -1: intersecting
}
//在一個已排序的陣列裡，取得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) {
            //在這邊確認拿到的是"第一個"大於等於目標值的數字
            while(mid > 0 && arr[mid-1] === target){
                mid--
            }
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left
}

100%過關!!(https://app.codility.com/demo/results/training7T4RZ2-QP8/)

Claire's Blog