Tìm phần tử nhỏ thứ k của ma trận vuông

Duc_Khai_Tong · November 18, 2018, 9:53am

Em/ mình có đề bài.
Cho một ma trận A có kích thước n×n mà các phần tử trên cùng một hàng hoặc cùng một cột được sắp xếp không giảm (phần tử phía trước nhỏ hơn hoặc bằng phần tử phía sau). Viết chương trình tìm phần tử nhỏ thứ k của ma trận này
Mình đã làm cách đưa về mảng 1 chiều không sử dụng điều kiện cho là các phần tử sau lớn hơn phần tử trước trên cột hoặc hàng. Xin m.n cho ý tưởng khác

DLH06 · November 18, 2018, 11:54am

Bạn có thể đưa nó vào mảng 1 chiều kèm chỉ số hàng và cột của nó nhưng sort theo giá trị
Với c++ mình thì mình sẽ push vào vector giá trị, hàng, cột và viết hàm compare cho sort

Hoang_Anh9 · November 18, 2018, 12:03pm

Ý tưởng của bạn là đưa về mảng một chiều cũng đúng nhưng nếu chỉ có một mảng thì cách xử lý sẽ rắc rối phức tạp. Nên dùng một vector rồi push tất cả các giá trị của mảng vào vector, sau đó sorting cho vector. Cuối cùng là so sánh phần tử nhỏ thứ k của vector với các phần tử của mảng.

Duc_Khai_Tong · November 18, 2018, 1:32pm

mình đã làm cách đó rồi, ý mình là không biết cái giả thiết kia người ta cho để làm gì

noz1995 · November 18, 2018, 1:55pm

Có thể là để bạn chỉ lấy trong khoảng [k, k] phần tử cuổi cùng thôi?

Hoang_Anh9 · November 18, 2018, 2:10pm

có lẽ điều kiện đó của bài toán muốn bạn phải làm theo quy luật như thế này:
a00 < (a01 và a10) < (a02, a11, a20) < (a03, a12, a21, a30) < … < [a0(n-1), a1(n-2), … , a(n-2)1, a(n-1)0] < … < [a(n-2)(n-1), a(n-1)(n-2)] < a(n-1)(n-1)]
từ quy luật trên bạn thử nghĩ thuật toán xem sao
p/s: dấu nhỏ hơn nghĩa là nhỏ hơn hoặc bằng nhé, còn n-1, n-2 chỉ đại diện cho chỉ số mà thôi

Red_Sand · November 18, 2018, 5:26pm

Ý tưởng là sort lại ma trận theo chiều từ trái qua phải và hàng sau lớn hơn hàng trước.
1 2 3 4
5 6 7 8
…
13 14 15 16
Đệ quy:
Chia ma trận A thành 4 ma trận con
A1 A2
A3 A4
Sort A1, A4,

bởi vì A1 vốn đã nhỏ nhất và A4 đã lớn nhất
-> Merge sort A2, A3
-> sorted matrix.

vanhieu · November 19, 2018, 5:44am

Bạn biết cấu trúc map<int, int> của C++ không?

Bài này bạn chỉ duyệt mảng 1 lần và add từng phần tử vào map. Key của map là giá trị của mảng, value của map là gì cũng được(ở bài này value vô dụng).

Do map sort theo key rồi nên bạn chỉ cần for tới phần tử thứ k rồi in ra là được.

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n = 3;
	int a[n][n] = {
					{ 1, 3, 3},
					{ 4, 5, 6},
					{ 7, 8, 9}
				};
	map<int, int> m;
	for(int i = 0;i < n; ++i){
		for(int j = 0; j < n; ++j){
			m[a[i][j]] = 1;
		}
	}
	int k = 3;
	for(auto it : m){
		--k;
		if(!k) {
			cout << it.first;
			return 0;
		}
	}
}

Output: 4

#Update:
Theo tính chất của ma trận bạn nói, thì bạn chỉ cần tìm phần tử thứ k(ko tính trùng lặp) là xong mà nhỉ :))

rogp10 · December 12, 2018, 4:35am

Ban đầu mình đổ vào std::vector rồi std::make_heap.

Nhưng đều ko đúng với yêu cầu ^ chỉ lên

Hai cách trên đều là O(n^2) mem mình đọc đc trên g4g có một cách O(n) mem ntn.

: input n, a[1..n][1..n], k
: alias Tuple<data, row, col> triple;

auto H = min_heap<triple>.instantiate {
payload: a.row[1].transform_with_index((data, index) => triple(data, 1, index)), 
comparator: (u, v) => (u.data < v.data) };

while(k--) begin
   t = H.extract();
   if(t.row < n) H.insert(triple.instantiate(a[t.row+1][t.col], t.row+1, t.col));
end;
:output t.data

Thuật toán duyệt tất cả phần tử trong mảng, mỗi phần tử đúng một lần duy nhất, do heap ban đầu chứa phần tử từ cả n cột.
Số sau >= số liền trước, vì theo đề thì a[row+1][col] >= a[row][col].

Hoang_Anh9 · November 19, 2018, 6:48am

@vanhieu Cách này bạn ấy đã làm rồi

Red_Sand · November 19, 2018, 12:22pm

Cùng một hàng hoặc cùng một cột được sắp xếp không giảm nhé, không phải ma trận đã được sắp xếp.
1 4
2 5 cũng thoả mãn đề bài

tntxtnt · November 20, 2018, 2:58am

đều là O(k logn) sao ko dồn thành 1 mảng rồi tìm nth element tốn có O(n²)
nhầm nữa, O(n²) mới đúng

rogp10 · November 19, 2018, 1:21pm

Bạn làm thế nào mà O(k) zị

tntxtnt · November 19, 2018, 1:51pm

ý nhầm O(n) chứ :V

20 chả

#include <iostream>
#include <vector>
#include <queue>
//#include <algorithm>
using namespace std;

int main()
{
    int n, k; cin >> n >> k;
    vector<int> a(n*n); for (int& i : a) cin >> i;
    //nth_element(begin(a), begin(a)+k-1, end(a));
    //cout << a[k-1];
    struct A { int *p, n, operator<(const A& x)const { return *p > *x.p; } };
    priority_queue<A> q; for (int j = 0; j < n*n; j += n) q.push({&a[j], n});
    for (; --k; q.pop()) if (q.top().n) q.push({q.top().p+1, q.top().n-1});
    cout << *q.top().p;
}

cái kia có 2 dòng :V :V :V :V :V

edit: code khó hiểu hơn còn 4 dòng

rogp10 · November 20, 2018, 1:30am

Vẫn là O(klogn), vì có dùng heap

Red_Sand · November 19, 2018, 6:06pm

Thế này nhé:
Pseudo code:

Sort(matrix A) // Square matrix row = col
{
  if(A.rows == 2)
    {
       if(A_12 > A_21)
              {
                   exchange(A_12, A_21);
                   return;
              }
        return;
    }
  Partition A into four parts: A11, A12, A21, A22;
  Sort(A11);
  Sort(A22);
  Sort(A12);
  Sort(A21);
  Merge(A12, A21);
  return;
}

Merge(Matrix& A, Matrix& B) // A.size = B.size
{
   Matrix C = new Matrix with same size;
int Arow = 1, Acolumn = 1;
int Brow = 1, Bcolumn = 1;
//Copy the first row*column smallest elements of A and B to C
for(C: row)
  for(C: column)
   {
      if(A(Arow, Acolumn) <= B(Brow, Bcolumn)
       {
           C(row, column) = A(Arow, Acolumn);
           Acolumn++;
           if(Acolumn > A.column)
             {
                Acolumn = 1;
               Arow ++;
             }
        }
      else{
         C(row, column) = B(Brow, Bcolumn);
         Bcolumn++;
         if(Bcolumn> B.Bcolumn)
             {
                Bcolumn= 1;
               Bcolumn++;
             }
        }
   }
   do the same to copy the left over elements of A and B To B;
    copy C to A;
}

recursion:

T(n) = { 1 if n = 4;
         4T(n/4) + 3n/4 otherwise
        }

Với ma trận có tổng n phần tử, total time cost là: T = 3/4(nlog4(3) + nlog4(n))
Có thể coi như 3n/4(log4(n)).
Complexity: O(nlogn).
=> với ma trận siêu lớn, điều kiện đề bài không ảnh hưởng running time lắm.
Còn cách nhanh hơn là chia ma trận ra rồi xem k có nằm trong khoảng n/4-> 3n/4 không hay trong khoảng còn lại, rồi liên tục đệ quy. Nhưng cách này quá phức tạp nên mình chịu.

rogp10 · November 20, 2018, 8:33am

Vậy thì cũng ngang ngang với đổ ra mảng sort.

A.Mirzaian, E.Arjomandi, Selection in X+Y and matrices with sorted rows and columns, http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf thì nó ntn:

We call A ordered if elements in each row are in non-increasing order, and elements in each column are in non-decreasing order.

Nó ngược nên ta đổi qua cột không tăng với O(n).

update: https://chaoxuprime.com/posts/2014-04-02-selection-in-a-sorted-matrix.html

tntxtnt · November 20, 2018, 2:59am

select nth_element đơn giản trên ma trận nxn thì tốn O(n²) mới đúng :V Mấy ông này tìm được cách O(n) thì quá ngon rồi @_@

Red_Sand · November 20, 2018, 3:02am

Giảm từ log2 xuống log4 mà vế kia ko tăng, c = 3/4 là I tried my best rồi :v, k biết mấy ông trong tài liệu làm kiểu gì mà T(n) = O(n)

tntxtnt · November 20, 2018, 3:10am

log2 hay log4 cũng là log thôi ko giảm được bao nhiêu =) Vì log_ax = log_bx / log_ba nên log₄x = log₂x / log₂4 = log₂x / 2, 1/2 là hằng số nên vẫn là O(logn) thôi