Bài toán trong lớp nhập môn khoa học máy tính của tôi yêu cầu tôi tìm hai số nguyên lớn nhất trong một danh sách. Danh sách chỉ chứa các số nguyên và tôi có thể giả sử rằng có ít nhất 2 số nguyên trong danh sách
Vấn đề không nêu rõ số nguyên lớn nhất và lớn thứ hai có phải là số nguyên duy nhất hay không. Nói cách khác, nếu số nguyên lớn nhất trong danh sách là 34 và nó xuất hiện hai lần, tôi sẽ giả định rằng 34 có thể là số nguyên lớn nhất và lớn thứ hai. Vấn đề cũng không nêu rõ liệu chúng ta có thể thay đổi danh sách hay không. Tôi sẽ cho rằng chúng ta có thể thực hiện những thay đổi phá hoại đối với danh sách. Nói cách khác, chúng ta có thể thay đổi danh sách bằng cách thêm và xóa các mục, v.v.
Hàm tối đa trong Python
Với những giả định này, suy nghĩ đầu tiên của tôi là hàm max trong Python, hàm này sẽ trả về giá trị lớn nhất trong danh sách
integers = [1, 16, 3, 39, 26, 4, 8, 16] largest_integer = max[integers] # 39
Max là một hàm rất tiện dụng để tìm số nguyên lớn nhất trong danh sách, nhưng tôi cũng cần tìm số nguyên lớn thứ hai. Nếu tôi xóa số nguyên lớn nhất khỏi danh sách sau khi tìm thấy nó, thì số nguyên lớn thứ hai bây giờ phải là số nguyên lớn nhất mới. Tôi có thể gọi max trong danh sách lần thứ hai và lấy số nguyên lớn nhất tiếp theo
integers = [1, 16, 3, 39, 26, 4, 8, 16] largest_integer = max[integers] # 39 integers.remove[largest_integer] second_largest_integer = max[integers] # 26
Nếu thay đổi danh sách không phải là một tùy chọn và giả sử đây là một danh sách nhỏ các số nguyên vì lợi ích của bộ nhớ máy tính, tôi luôn có thể sao chép danh sách rồi thực hiện thao tác trên danh sách mới. Điều này sẽ giữ danh sách ban đầu, số nguyên, không sửa đổi
integers = [1, 16, 3, 39, 26, 4, 8, 16] # clone the list by slicing copy_of_integers = integers[:] # [1, 16, 3, 39, 26, 4, 8, 16] largest_integer = max[copy_of_integers] # 39 copy_of_integers.remove[largest_integer] second_largest_integer = max[copy_of_integers] # 26
Sử dụng hàm max để tìm số nguyên lớn nhất và lớn thứ hai trong danh sách có vẻ như là một giải pháp lý tưởng
Sắp xếp danh sách
Tùy chọn khác ngay lập tức xuất hiện trong đầu tôi là sắp xếp danh sách. Sau khi danh sách các số nguyên được sắp xếp, thật dễ dàng để chọn ra các số nguyên lớn nhất và lớn thứ hai. Python có chức năng sắp xếp tích hợp thực hiện tất cả công việc. Nó trả về một danh sách được sắp xếp mới
integers = [1, 16, 3, 39, 26, 4, 8, 16] sorted_integers = sorted[integers] # [1, 3, 4, 8, 16, 16, 26, 39] largest_integer = sorted_integers[-1] # 39 second_largest_integer = sorted_integers[-2] # 26
Khả năng lập chỉ mục danh sách được sắp xếp mới bằng cách sử dụng [-1] cho mục cuối cùng trong danh sách và [-2] cho mục thứ hai đến cuối cùng trong danh sách là tuyệt vời trong Python. Nếu việc sử dụng -1 và -2 có vẻ ít rõ ràng hơn, tôi có thể sắp xếp danh sách theo thứ tự giảm dần [ đảo ngược ]. Khi sắp xếp ngược lại, số nguyên lớn nhất và lớn thứ hai sẽ có chỉ số lần lượt là 0 và 1
integers = [1, 16, 3, 39, 26, 4, 8, 16] sorted_integers = sorted[integers, reverse=True] # [39, 26, 16, 16, 8, 4, 3, 1] largest_integer = sorted_integers[0] # 39 second_largest_integer = sorted_integers[1] # 26
Rõ ràng là có chi phí sắp xếp danh sách các số nguyên, nhưng giải pháp rất rõ ràng và trực quan. tôi thích nó
Sử dụng Set to Remove Duplicates
Tôi bắt đầu nghĩ xem mình sẽ làm gì nếu bài toán nói rằng cùng một số không thể là số nguyên lớn nhất và lớn thứ hai. Nói cách khác, chúng phải là những giá trị duy nhất
Rõ ràng người ta có thể chỉ lặp qua danh sách cho đến khi tìm thấy hai số nguyên duy nhất lớn nhất. Tuy nhiên, tôi nghĩ ngay đến set trong Python, được đảm bảo chỉ chứa các giá trị duy nhất. Chúng tôi có thể tạo một bộ từ danh sách, điều này sẽ loại bỏ các bản sao. Sau đó, chúng ta có thể tìm thấy hai giá trị lớn nhất trong tập hợp bằng cách sử dụng hàm max
Lưu ý rằng tôi đã thay đổi danh sách các số nguyên để bao gồm 39 hai lần, nhưng dựa trên giả định mới 39 không thể là số nguyên lớn nhất và lớn thứ hai trong danh sách. Các giá trị phải là duy nhất và thiết lập sẽ loại bỏ các giá trị dư thừa đối với tôi
integers = [1, 16, 3, 39, 26, 4, 8, 16, 39] unique_integers = set[integers] # set[[1, 3, 4, 39, 8, 16, 26]] largest_integer = max[unique_integers] # 39 unique_integers.remove[largest_integer] second_largest_integer = max[unique_integers] # 26
Việc sử dụng tập hợp giải quyết vấn đề về tính duy nhất khá độc đáo
heapq. lớn nhất
Theo tài liệu, heapq cung cấp triển khai thuật toán hàng đợi heap, còn được gọi là thuật toán hàng đợi ưu tiên. Nó có một phương thức, được gọi là lớn nhất, có thể được sử dụng để tìm 2 số nguyên lớn nhất
integers = [1, 16, 3, 39, 26, 4, 8, 16] # get 2 largest values largest_integers = heapq.nlargest[2, integers] # [39, 26] largest_integer = largest_integers[0] # 39 second_largest_integer = largest_integers[1] # 26
Sự kết luận
Tôi phải nói rằng tôi cực kỳ thích học Python, đó là lý do tại sao tôi đánh chết vấn đề này. Tôi chưa xem câu trả lời cho vấn đề do giảng viên cung cấp trong khóa học, nhưng tôi sẽ xem sau hôm nay. ] Tôi thực sự khuyên bạn nên tận dụng khóa đào tạo trực tuyến miễn phí. Tôi đã học được rất nhiều về các thuật toán, cấu trúc dữ liệu và lập trình Python nhờ có rất nhiều tài nguyên trực tuyến tuyệt vời