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