Đố fun - tìm phần tử nhỏ thứ n trong array (không sort)

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 m phần, tìm min của mỗi phần thì sau khi tìm ta có được m số nhỏ nhất.
Vậy số lớn nhất trong m số này = số nhỏ thứ m mà ta cần tìm.

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(n²) 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 n² 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

chứng minh O(n) http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_writtenlec2.pdf

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:

• Nếu arr chỉ chứa 1 phần tử hiển nhiên nó là kết quả
• Chia array thành từng block, mỗi block tối đa 5 phần tử, lấy median của từng phần tử này dưa và 1 mảng medians:

• Gọi m là kích thước mảng medians, gọi pivot = kthSmallestElement(medians, m, m/2)
• Gọi 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)
  Độ phức tạp: O(N) time + O(N) extra space
  Chứng minh độ phức tạp: http://www.cc.gatech.edu/~mihail/medianCMU.pdf

[spoiler]Đó 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[/spoiler]
Cách giải tào lao rồi

unordered_set/unordered_map có thứ tự đâu, làm sao biết phần tử nào lớn nhất mà remove? Phải tìm phần tử lớn nhất trong hashset mỗi lần remove thì tốn O(n) tìm kiếm cho 1 lần remove, ~O(n^2) lần tổng cộng rồi.

dễ ăn thế thì đâu có thuật toán kia