Maxima & minima của mảng

Question

Một dãy số n được đưa ra, trong đó n là số chẵn. Số lượng n tối đa cũng như số lượng tối thiểu này cần được xác định. Tôi cần biết các so sánh cần thiết?

Answer 1

Có thể thực hiện trong thời gian O (n).

Bạn có thể kiểm tra link này để tham khảo

Answer 2

Nó có thể được thực hiện bằng 3*n/2-2 so sánh.

Đối với n == 2, chỉ cần so sánh hai số. Bây giờ giả sử chúng ta có tối thiểu và tối đa cho số n-2 đầu tiên. So sánh hai số còn lại, sau đó so sánh số lớn hơn với số tối đa trước đó và nhỏ hơn số tối thiểu trước đó.

Answer 3

Đối với mảng chưa được phân loại, nó có thể được thực hiện trong khoảng so sánh 1.5n. Bạn có thể làm điều đó bằng cách so sánh các cặp phần tử của một mảng và lưu trữ min và địa phương max. Bạn đã thực hiện n/2 so sánh để tìm kiếm (số người tối đa) và n/2 để tìm số phút. Như vậy, tổng số là n trong giai đoạn này.

Bây giờ bạn đi qua các địa phương tối đa và tối thiểu và tìm tối đa và tối đa toàn cầu. Điều này cũng sẽ thực hiện các so sánh n/2. Do đó n + n/2 = 1.5n.

Nếu mảng được sắp xếp, bạn có thể tìm thấy nó mà không cần bất kỳ sự so sánh, vì số lượng thấp nhất là trên vị trí 0 và cao nhất vào vị trí N - 1.