Đợt trước có bạn nào đăng bài toán tìm phần tử nhỏ thứ nhì trong array. Cách giài sử dụng 2 biến, time complexity là O(n).
Nay mình mạn phép hỏi bải toán tổng quát hơn, tìm phần tử nhỏ thứ n của array mà không dùng sort. Mọi người thử đưa cách giải cùng time complexity và space complexity nhé ;).
Tìm phần tử nhỏ thứ m trong n phần tử nhé.
Dùng cây nhị phân :)) space O(n), time O(nlogn)
Sai mất rồi 
chia như thế nào?
nếu mảng là
1 2 3 4 5 6.
Tìm phần tử min thứ 2 chẳng hạn.
thế chia mảng làm 2:
1 2 3 và 4 5 6
=> được 1 và 4
=> 4 là phần tử nhỏ thứ 2???
Ờ nhỉ, tks Sáng Béo đã chỉ chỗ sai.
Mình đang thử làm 1 cách mà làm xong code chạy rồi xong nghĩ lại thấy thuật toán có chỗ sai nên thôi không đưa lên nữa. 
cái này giống như median finding, có thuật toán tìm O(n) rồi mà, trong cuốn Algo của MIT có đó
trong C++ thì có hàm nth_element thì phải: http://en.cppreference.com/w/cpp/algorithm/nth_element
Complexity
Linear in std::distance(first, last) on average
hic, làm mà O(n^2)… cảm thấy kém cỏi…
Nếu dùng hàm build heap trong heapsort thì độ phức tap là nlogn, bộ nhớ là O(1)
Mảng chưa đc sắp xếp nhé bạn ;))
Đố fun là suy nghĩ cách giải chứ lôi wiki hay sgk ra thì còn gì hay nữa
cái này mình học qua ở chương sắp xếp rồi, nên muốn suy nghĩ cũng ko được có điều cách chứng minh O(n) thì rối lắm. Học cái gì gây ngạc nhiên là nhớ tới hết đời.
ý tưởng là phân mảnh như quicksort ấy, nhưng khi phân mảnh ra thì ko phân mảnh tiếp ở 2 mảng mà chỉ ở 1 mảng thôi. Cái này trung bình là O(n), có lẽ là cách mà nth_element xài, nhưng vẫn vướng O(n2) worst case như quicksort, nên phải có trick nữa để bảo đảm O(n) worst case. Trick này mình cũng ko nhớ nhưng mà có liên quan tới chia 5 gì đó để chọn pivot sao cho lúc phân mảnh được tệ nhất là mảnh 3 phần và mảnh 7 phần. Từ đó bảo đảm ko bao giờ phân mảnh mà có 1 mảnh chỉ có 1 phần tử, nên worst case ko còn n2 nữa. Chứng minh nó là O(n) thì mới là vật vã
Tìm phần tử nhỏ thứ m trong mảng n phần tử: Suy ra ta có thể hiểu đơn giản là số đó phải nhỏ hơn đúng m-1 phần tử trong mảng.
Thuật toán:
+B1: Gọi 2 biến đếm : đếm nhỏ =0;
+B2:Cho chạy từ 0->n-1
+B3:So sánh a[0] với a[1]…a[n-1]. Mỗi lần nhỏ hơn thì tăng đếm lên 1. Kết thúc mảng nếu đếm = m-1 thì tìm được phần tử đó. Kết thúc. Nếu không ta thực hiện bước kế tiếp đem đếm về 0;
+B4: So sánh a[1] với a[0]…a[n-1] điều kiện bỏ qua a[1] khi chạy vòng lặp từ a[0] lên a[n-1]. Lặp lại bước 3.
Theo mình chuyển cái mảng sang cây nhị phân tìm kiếm rùi tìm cho nhanh. Mà dùng Cây nhị phân tìm kiếm thì có gọi là Soft không nhỉ?
Đếm số lần nhỏ hơn là ra thôi, theo mình nghĩ vậy. Có ai có ý kiến giống mình không.
Ý tưởng đầu tiên là phân 3 phần và tìm trong mỗi phần, cách này khá giống quick sort
def kth(a,k):
if k==1:
return min(a)
n=len(a)
pivot=a[random.randint(0,n-1)]
less=filter(lambda x:x<pivot,a)
nEq=a.count(pivot)
greater=filter(lambda x:x>pivot,a)
nL=len(less)
nG=len(greater)
if k<=nL:
return kth(less,k)
elif k<=nL+nEq:
return pivot
return kth(greater,k-nL-nEq)
Để cải tiến thuật toán ta phải tìm cách cho pivot chia đôi được mảng , ý tương tự thuật toán median of median
2/5n<indexof(pivot)<4/5n
Sau khi cải tiến
def median5(a): #find median size<=5
n=len(a)
return sorted(a)[n//2]
def kth(a,k):
if k==1:
return min(a)
n=len(a)
median=[]
i=0
while i<n//5:
median.append(median5(a[i*5:i*5+5]))
i+=1
if n%5:
median.append(median5(a[i*5:]))
if len(median)==1:
pivot=a[0]
else:
pivot=kth(median,len(median)//2)
less=filter(lambda x:x<pivot,a)
nEq=a.count(pivot)
greater=filter(lambda x:x>pivot,a)
nL=len(less)
nG=len(greater)
if k<=nL:
return kth(less,k)
elif k<=nL+nEq:
return pivot
return kth(greater,k-nL-nEq)
Độ phức tạp của thuật toán O(n).
chạy thử trên http://ideone.com/HAaIwg
hàm median5 xài sorted “ăn gian” rồi kìa
giỡn thôi, 5 phần tử thì sort coi như O(1) nên có xài bubble sort cũng chả ai cấm. Nhưng mà với 5 phần tử, số lượng nhỏ thì xài cách sort tối ưu, hồi đó ông thầy thách đố chỉ với 7 lần so sánh hãy sắp xếp 5 phần tử, tưởng dễ mà ko phải dễ Nếu có bài tập về if else thì cho bài tập này được đó
bạn có thể viết code ra không? đọc thuật toán khó hình dung qúa.
thấy có vẻ giống cái mình vừa làm, nếu là giống thì mình sẽ chỉ ra case bị sai :3
Sử dụng thuật toán Median of medians:
Ta gọi hàm int kthSmallestElement(int arr[], int n, int k) là hàm tìm phần tử nhỏ thứ k của mảng arr có n phần tử. Hàm int partition(int arr[], int n, int pivot) là hàm phân tập, chia arr thành 2 phần, bên trái <= pivot và bên phải > pivot (giống quicksort), hàm return về số lượng phần tử <= pivot
Thực hiện thuật toán:
pivot = kthSmallestElement(medians, m, m/2)
x = partition(arr, n, pivot). Nếu x == k thì giá trị cần tìm là pivot, nếu x > k thì return kthSmallestElement(arr, x, k), ngược lại return kthSmallestElement(arr+x, n-x, k-x)Đó là ai muốn chơi thuật, còn chơi chiêu, sử dụng sức mạnh của ngôn ngữ lập trình thì có unordered_set (nếu các giá trị có thể dùng nhau thì unordered_multiset, nếu ép không cho dùng C++11 thì dùng unordered_map để thay thế) trong C++ hay HashSet trong Java, độ phức tạp trung bình của mỗi truy vấn là O(1). Đưa từng phần tử vào set, nếu size > k thì remove phần tử lớn nhất ra khỏi set. Cuối cùng kết quả chính là phần tử lớn nhất trong set.[/spoiler]
[spoiler]Như vậy: N phần tử, mỗi phần tử insert 1 lần, và sẽ có N-K lần remove phần tử ra khỏi set. chi phí O(2N - K), có thể xem O(N). Và thêm O(K) extra space
Cách giải tào lao rồi
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?