Tôi gặp sự cố này "Triển khai phương thức này để trả về tổng của hai số lớn nhất trong một mảng nhất định".Độ phức tạp của thuật toán
tôi giải quyết nó theo cách này:
public static int sumOfTwoLargestElements(int[] a) {
int firstLargest = largest(a, 0, a.length-1);
int firstLarge = a[firstLargest];
a[firstLargest] = -1;
int secondLargest = largest(a, 0, a.length-1);
return firstLarge + a[secondLargest];
}
private static int largest(int s[], int start , int end){
if (end - start == 0){
return end;
}
int a = largest(s, start, start + (end-start)/2) ;
int b = largest(s, start + (end-start)/2+1 , end);
if(s[a] > s[b]) {
return a;
}else {
return b;
}
}
Giải thích: Tôi thực hiện một phương pháp 'largeset'. Phương thức này chịu trách nhiệm lấy số lớn nhất trong một mảng nhất định.
Tôi gọi phương thức kéo lần trong cùng một mảng. Cuộc gọi đầu tiên sẽ nhận được số lớn nhất đầu tiên. Tôi đặt nó sang một bên thành biến và tôi thay thế nó bằng số '-1' vào mảng. Sau đó, tôi gọi lần thứ hai là medhod lớn nhất.
Một số người có thể cho tôi biết sự phức tạp của bản ngã này là gì? vui lòng
Bạn có thể tìm thấy cả hai con số trong đầu tiên vượt qua và tha đèo thứ hai. Nó sẽ không thay đổi sự phức tạp nhưng nó sẽ chạy nhanh hơn. :-) – assafmo
+1 cho nhận xét ở trên. Ngoài ra nếu nó chỉ là một danh sách các con số, thì có nhiều cách giải khác nhau ... nếu bạn sử dụng một cơ chế như đếm số vv với không gian thừa không đáng kể và độ phức tạp thời gian O (n) ... – dharam
phức tạp là của người đọc trong tương lai của mã này, thời gian họ dành cho việc tìm ra cách thức hoạt động này, khi một thuật toán đơn giản hơn nhiều sẽ thực hiện công việc. Không có lợi ích rõ ràng để đệ quy, hoặc lý do tại sao hai đi qua các thiết lập là cần thiết.Và thuật toán về cơ bản bị hỏng (trả về kết quả không chính xác) khi hai số nguyên lớn nhất trong mảng đều nhỏ hơn -1. Accckkk! – spencer7593