Hướng dẫn partition trong python
Mục đíchChia một mảng ra thành hai cụm: một cụm thỏa điều kiện, và cụm còn lại. Cài đặtSử dụng mảng phụdef partition(a, pred): head = [x for x in a if pred(x)] tail = [x for x in a if not pred(x)] return head + tail, len(head) Không dùng mảng phụÝ tưởng chính là sử dụng một biến phụ chứa vị trí trong mảng A mà nếu phần tử đang xét thỏa điều kiện sẽ được chuyển vào. def partition(a, pred): okay_idx = 0 for i, x in enumerate(a): if pred(x): a[okay_idx], a[i] = a[i], a[okay_idx] # swap okay_idx += 1 return a, okay_idx Độ phức tạpThời gian chạyO(n)Bộ nhớ cần thiếtO(n) nếu sử dụng mảng phụ, hoặc O(1) nếu khôngỨng dụngỨng dụng nổi tiếng nhất là thuật toán QuickSort do Tony Hoare sáng tạo ra. Thuật toán QuickSort sắp xếp một mảng với độ phức tạp trung bình là O(n*logn) với n là số lượng phần tử trong mảng. Độ phức tạp trong trường hợp xấu nhất có thể là O(n*n). Sau đây là một cài đặt dễ hiểu của QuickSort. Cài đặt này chỉ dùng để thể hiện ý tưởng chứ không nên dùng trong các ứng dụng. Ý tưởng chủ đạo là lấy ra một phần tử nào đó trong A (tức là A' chỉ còn N-1 phần tử) gọi là pivot, ngăn A' thành hai cụm (một cụm nhỏ hơn pivot, một cụm còn lại). Tiếp tục gọi đệ quy để sắp xếp hai cụm đó và nối chúng lại với nhau thông qua pivot. def quicksort(a): if len(a) <= 1: return a pivot = a[-1] a, pivot_idx = partition(a[ : -1], lambda x: x <= pivot) return quicksort(a[ : pivot_idx]) + [pivot] + quicksort(a[pivot_idx : ]) import itertools for l in range(8): a = range(l) for p in itertools.permutations(a): p = list(p) assert quicksort(p) == a Bài toán mở rộng
Các bạn có thể trao đổi về cách giải bài các bài toán mở rộng này với độ phức tạp trung bình O(n) trong diễn đàn. Hàm split() trong Python chia chuỗi theo delimeter đã cho (là space nếu không được cung cấp) và trả về danh sách các chuỗi con; nếu bạn cung cấp đối số num thì chia chuỗi thành num + 1 chuỗi con. Cú phápCú pháp của split() trong Python: str.split(str="", num=string.count(str)) Chi tiết về tham số:
Ví dụ sau minh họa cách sử dụng của split() trong Python. str1 = "Line1-Python Line2-Java Line3-PHP"; print("Test 1:"); arr1 = str1.split(); for arr in arr1: print (arr); print("\nTest 2:"); arr1 = str1.split(' ', 1); for arr in arr1: print (arr); Chạy chương trình Python trên sẽ cho kết quả: Test 1: Line1-Python Line2-Java Line3-PHP Test 2: Line1-Python Line2-Java Line3-PHP |