kết quả từ 1 tới 4 trên 4

In ra mảng gồm các phần tử nhỏ thứ i/4

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 367175
    Bài gửi
    4
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: In ra mảng gồm các phần tử nhỏ thứ i/4

    Bài này sẽ dùng 2 loại heap: min vả max heap. Tuy nhiên đề bài và ví dụ hình như bị lệch index rồi. Bạn hỏi thầy lại cho kỹ nhé, tốt nhất là làm rõ ví dụ ra.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 367175
    Bài gửi
    4

    Reply: In ra mảng gồm các phần tử nhỏ thứ i/4

    Mình ghi nhầm: Cho 1 dãy A gồm N số, N < 10000000. In ra mảng B gồm các phần tử B[i] là phần tử nhỏ thứ floor(i/4) trong dãy từ A[0] tới A[i]. Ví dụ nếu A là 5, 3, 4, 6, 7, 2, 8, 2 thì B là 5, 3, 3, 3, 4, 3, 3, 2. Cám ơn bạn.

  5. Đã cảm ơn LittleABC:


  6. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    874

    Reply: In ra mảng gồm các phần tử nhỏ thứ i/4

    Như mình đã nói, bạn dùng 2 heap: max và min. Max heap[i] chứa 25% của mảng A[0..i], còn min heap chứa 75% của mảng A[0..i].
    - Nếu A[i] >= maxHeap.top thì đưa A[i] vào minHeap.
    - Nếu A[i] < maxHeap.top thì chuyển maxHeap.top vào minHeap, sau đó đưa A[i] vào maxHeap.
    - Cuối cùng lưu ý trường hợp maxHeap.size < i/4 thì phải chuyển minHeap.top vào maxHeap.
    - Tại mỗi i, sau khi thực hiện các bước trên thì B[i] = maxHeap.top.
    Thuật toán có độ phức tạp O(n log n). Với N = 10000000 thì cái này vừa đúng thời gian.

  7. Đã cảm ơn tengiday: