Thuật toán kiểm tra xem trong mảng S và T là số nguyên s và t sao cho s + t = k nếu k được cho số

Question

Tôi đang cố gắng thực hiện thuật toán lấy hai mảng, S và T của n số nguyên và k. Thuật toán kiểm tra xem các mảng có số nguyên s và t vì vậy s + t = k. (S trong S và t trong T.) Thuật toán được cho là có thời gian chạy của O (n log n).

Đã cố gắng nghĩ về thứ gì đó sắp xếp mảng T và sử dụng cho vòng lặp đi qua S và sử dụng tìm kiếm nhị phân để xem tôi có tìm số nguyên như k - S [i] cho mọi phần tử trong S. Nhưng điều đó sẽ luôn có thời gian chạy lớn hơn n log n, tôi nghĩ vậy.

Không tìm kiếm ai đó để viết mã. Chỉ yêu cầu ở đây để có được một số ý tưởng.

Answer 1

Sắp xếp hai danh sách, đây là O (n log n).

Sau đó, thiết lập hai trình lặp. Một trình lặp bắt đầu tại giá trị thấp nhất trong S và tiếp tục thông qua các giá trị ngày càng tăng trong S. Trình lặp khác bắt đầu tại giá trị cao nhất trong T và lặp qua các giá trị giảm dần.

Lặp lại như sau:

• nếu các giá trị hiện tại tổng hợp cho một số lớn hơn k, thúc đẩy các iterator T. Điều này sẽ làm giảm tổng.
• nếu giá trị hiện tại tính tổng số nhỏ hơn k, hãy chuyển tiếp trình lặp S. Điều này sẽ tăng tổng.
• nếu các giá trị hiện tại tính tổng cộng là k, sau đó thoát với thành công.

Giai đoạn thứ hai này sẽ gây ra, nhiều nhất là tiến trình 2N và do đó là O (n). Vì vậy, tổng phức tạp là O (n log n).

Điều này có cùng độ phức tạp như tìm kiếm nhị phân lặp lại, nhưng thuật toán này sẽ nhanh hơn, đặc biệt là đối với số lớn n.

Answer 2

Thuật toán bạn đã chỉ định thực sự có thời gian chạy O (n log n), giả sử rằng tổng số phần tử trong cả hai mảng là O (n). Bạn có thể thấy điều này ở đây:

• Sắp xếp một trong những mảng (O (n log n))
• Đối với mỗi phần tử của mảng khác: (O (n) lặp đi lặp lại)
  • Làm một nhị phân tìm kiếm để xem nếu các yếu tố bổ sung là trong mảng khác (O (log n) thời gian)

bước đầu tiên cần có thời gian O (n log n), và bước thứ hai bao gồm O (n) các phép lặp của một thuật toán O (log n), do đó cũng mất thời gian O (n log n). Vì O (n log n) + O (n log n) = O (n log n), thuật toán của bạn chạy trong thời gian O (n log n). Vì vậy, có vẻ như bạn đã có chính xác thuật toán mà bạn đang tìm kiếm!

Hy vọng điều này sẽ hữu ích!

Answer 3

Cách tiếp cận của bạn có vẻ chính xác; đầu tiên sắp xếp các mảng, hai hoạt động O (n log n), và sau đó bạn thực hiện các tìm kiếm nhị phân n, mỗi lần là O (log n).

Answer 4

Sắp xếp là O (n log n). Sau đó, đối với mỗi phần tử O (n) đầu tiên, bạn có tìm kiếm O (log n) cho một phần tử phù hợp. Có vẻ như tổng cộng O (n log n) (từ O (f) + O (f) = O (f) cho bất kỳ hàm f nào).

Answer 5

Sắp xếp cả hai mảng. Bước qua chúng trong đối diện với chỉ đường. Nếu tổng của hai phần tử nhỏ hơn k tiến tới con trỏ "tăng", nếu nó lớn hơn k, hãy làm tròn con trỏ đang giảm. Phương pháp này có thể chậm hơn một chút so với chỉ phân loại một trong các mảng, nhưng vượt qua cuối cùng chắc chắn là nhanh hơn. Và có lẽ ngắn hơn, bởi vì phần đầu và phần đuôi của hai mảng có thể bị bỏ qua (bị cắt đi).

Answer 6

Tuy nhiên, một phương pháp khác: lưu trữ một trong các mảng trong một hashtable (O (N)). Thực hiện chuyển tuyến tính qua phương thức kia (O (N)) và cho mọi elem thực hiện tra cứu k-elem trong Hashtable. Tổng thời gian chạy: 2 * O (N): = O (N). Lợi nhuận!