Diberikan sebuah larik yang berisi N titik, temukan K titik terdekat dengan titik asal (0, 0) pada bidang 2D. Anda dapat mengasumsikan K jauh lebih kecil dari N dan N sangat besar.

Misalnya:

    given array: (1,0), (3,0), (2,0), K = 2 
        Result = (1,0), (2,0)  

(hasil harus dalam urutan menaik berdasarkan jarak)

Kode:

import java.util.*;

class CPoint {
    double x;
    double y;
    public CPoint(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

public class KClosest {
    /**
     * @param myList: a list of myList
     * @param k: the number of closest myList
     * @return: the k closest myList
     */
    public static CPoint[] getKNearestPoints(CPoint[] myList, int k) {

        if (k <= 0 || k > myList.length)  return new CPoint[]{};                                
        if (myList == null || myList.length == 0 )  return myList; 

        final CPoint o = new CPoint(0, 0); // origin point

        // use a Max-Heap of size k for maintaining K closest points
        PriorityQueue<CPoint> pq = new PriorityQueue<CPoint> (k, new Comparator<CPoint> () {
            @Override
            public int compare(CPoint a, CPoint b) {
                return Double.compare(distance(b, o), distance(a, o));  
            }
        });

        for (CPoint p : myList) {   // Line 33
            // Keep adding the distance value until heap is full. // Line 34
            pq.offer(p);            // Line 35
            // If it is full        // Line 36
            if (pq.size() > k) {    // Line 37
                // Then remove the first element having the largest distance in PQ.// Line 38
                pq.poll();          // Line 39  
            }  // Line 40
        }       
        CPoint[] res = new CPoint[k];
        // Then make a second pass to get k closest points into result. 
        while (!pq.isEmpty()) {     // Line 44
            res[--k] = pq.poll();   // Line 45                   
        }                           // Line 46

        return res;
    }

    private static double distance(CPoint a, CPoint b) {        
        return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    }

}

Pertanyaan:

  1. Berapa kompleksitas waktu untuk baris 35, baris 39, mandiri dan terpisah?

  2. Berapa kompleksitas waktu untuk baris 35 - 40 (Secara keseluruhan) ?

  3. Berapa kompleksitas waktu untuk baris 44 - 46 (Secara keseluruhan) ?

  4. Berapa kompleksitas waktu keseluruhan untuk seluruh metode getKNearestPoints(), dalam kasus terbaik, terburuk, dan rata-rata? Bagaimana jika n >> k ? dan bagaimana jika kita tidak memiliki n >> k ?

Sebenarnya pertanyaan-pertanyaan ini adalah beberapa pertanyaan selama wawancara teknis saya, tetapi saya masih agak bingung. Bantuan apa pun dihargai.

3
Peter 8 Oktober 2017, 07:52
2
Ini sangat mirip dengan pekerjaan rumah. Apa sebenarnya yang Anda bingungkan? Menurut Anda apa jawabannya dan mengapa?
 – 
Krease
8 Oktober 2017, 08:00
Saya menjawab berikut selama wawancara: Q1: log(K), log(K), Q2: log(K) atau log(K) ^ 2 Q3: klog(K) Q4: NlogK + klogK tapi secara keseluruhan adalah NlogK? saya tidak yakin
 – 
Peter
8 Oktober 2017, 08:03
1
Saya tahu untuk PQ, semua operasi seperti tambah/tawarkan, hapus/jajak pendapat membutuhkan OlogK, kecuali mengintip adalah O1. tetapi untuk pertanyaan-pertanyaan ini secara khusus. aku benar-benar tersesat..
 – 
Peter
8 Oktober 2017, 08:14

1 menjawab

Jawaban Terbaik

Dari kelihatannya, saya pikir orang yang menulis kode ini pasti tahu jawaban atas pertanyaan-pertanyaan ini.

Bagaimanapun, Antrian Prioritas di sini didasarkan pada implementasi Max Heap.

Jadi, kompleksitasnya adalah sebagai berikut:

Baris 35 - O(log k) Waktu untuk menyisipkan elemen di heap. Pendekatan bottom up diikuti di heap pada saat penyisipan.

Baris 37 - O(1), Waktu untuk memeriksa ukuran tumpukan, umumnya dipertahankan bersama dengan tumpukan.

Baris 39 - O(log k), Waktu untuk menghilangkan kepala tumpukan, pendekatan heapify pada akar tumpukan diterapkan untuk menghilangkan bagian atas tumpukan tumpukan.

Baris 35-40: Dari kompleksitas di atas kita dapat melihat bahwa kompleksitas keseluruhan dari satu iterasi adalah O(log k). Loop ini berjalan untuk elemen n, sehingga kompleksitas keseluruhannya adalah O(n log k).

Baris 44-46: Kompleksitas pemeriksaan ukuran heap lagi O(1), dan polling adalah O(log k). Jadi kami melakukan polling k kali. Kompleksitas keseluruhan loop akan menjadi O(k log k).

Kompleksitas keseluruhan akan tetap O(n log k).

Ini adalah tempat yang bagus untuk mempelajari topik ini.

4
harmands 8 Oktober 2017, 12:34
Hai! jawaban ini sangat membantu. Tapi saya masih agak bingung di Line 35-40. Katakanlah ketika PQ ini penuh, maka akan ada (n - k) kali, pq.offer(p); dan pq.poll(); harus dijalankan bersama. Itu seharusnya O(logk) + O(logk) , kan? tetapi mengapa kami masih menganggapnya sebagai runtime O(logk)?
 – 
Peter
8 Oktober 2017, 08:19
2
Oke, untuk menempatkannya secara matematis, O(logk)+O(logk) = O(2logk)=O(logk^2)=O(logk), maksud saya mereka dapat ditulis dalam semua cara itu.
 – 
harmands
8 Oktober 2017, 08:22
2
Itu masuk akal! Terima kasih! Hanya satu pertanyaan lagi, mengapa kita bisa "mengurangi" waktu "melakukan umpan kedua untuk mendapatkan k poin terdekat ke hasil". (klogk)? Secara keseluruhan adalah O(nlogK), tetapi tidak O(nlogk) + O(klogk)
 – 
Peter
8 Oktober 2017, 08:22
1
Oh! apakah karena N >> K, jadi bisa di drop. Saya mendapatkannya. Terima kasih banyak!
 – 
Peter
8 Oktober 2017, 08:27
Ya, semacam, itulah alasannya.
 – 
harmands
8 Oktober 2017, 08:29