Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần, hãy tìm một vị trí thứ i trong dãy sao cho phần tử thứ i có giá trị bằng i.
Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần, hãy tìm một vị trí thứ i trong dãy sao cho phần tử thứ i có giá trị bằng i.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Để tìm vị trí thứ i trong dãy số sao cho phần tử thứ i có giá trị bằng i, ta có thể sử dụng phương pháp chia để trị như sau:
1. Tìm giá trị trung bình của left và right: mid = (left + right) // 2
2. Nếu giá trị tại vị trí mid bằng mid, tức là A[mid] == mid, thì trả về mid
3. Nếu giá trị tại vị trí mid lớn hơn mid, tức là A[mid] > mid, thì tiếp tục tìm vị trí thích hợp trong đoạn từ left đến mid-1
4. Nếu giá trị tại vị trí mid nhỏ hơn mid, tức là A[mid] < mid, thì tiếp tục tìm vị trí thích hợp trong đoạn từ mid+1 đến right
5. Nếu không tìm được vị trí thích hợp nào, tức là left > right, thì trả về -1
Ví dụ
Kết quả sẽ là "Vị trí thích hợp là: 3", tức là phần tử thứ 3 trong dãy A có giá trị bằng 3.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Đang tải chế độ Học...
Dành cho bạn Hot
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Để tìm số lần xuất hiện của K trong một dãy số chưa được sắp xếp bằng phương pháp chia để trị, ta có thể sử dụng đệ quy và chia dãy số ban đầu thành hai phần. Tiếp tục chia đến khi dãy số chỉ còn một phần tử hoặc không có phần tử nào
Với đầu vào là một dãy số A và một số K, hàm countNum sẽ trả về số lần xuất hiện của K trong dãy số A. Ví dụ
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Để thiết lập hai hàm firstInd và lastInd bằng kĩ thuật chia để trị, ta có thể áp dụng phương pháp tương tự như khi tìm kiếm số lần xuất hiện của một phần tử trong dãy số bằng kĩ thuật chia để trị. Cụ thể, ta sẽ chia dãy số thành hai nửa và tìm kiếm đệ quy trên từng nửa đó.
Ví dụ:
Kết quả trả về:
- Ta có thể sử dụng hàm firstInd và lastInd đã thiết kế để giải quyết bài toán tìm số lần xuất hiện của một số trong một dãy số.
Giả sử ta cần tìm số lần xuất hiện của số C trong dãy A đã sắp xếp tăng dần. Đầu tiên, ta sử dụng hàm firstInd để tìm chỉ số của phần tử đầu tiên có giá trị bằng C, sau đó sử dụng hàm lastInd để tìm chỉ số của phần tử cuối cùng có giá trị bằng C. Nếu cả hai hàm đều trả về giá trị khác -1, số lần xuất hiện của C trong dãy A sẽ là hiệu của chỉ số của phần tử cuối cùng và phần tử đầu tiên cộng thêm 1.
Vì mỗi lần gọi hàm firstInd và lastInd đều có độ phức tạp O(logn), nên độ phức tạp của giải pháp này sẽ là O(logn).
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập