目錄
- 題目
- 思路
-
- 個人思路
- 書中給的解法筆記
- 實作
- 效果展示
- 總結
題目
思路
個人思路
- 暴力分類
O ( m 2 ) O(m^2) O(m2)的複雜度進行分類， O ( n ) O(n) O(n)的複雜度進行比較，總複雜度 O ( m 2 n ) O(m^2n) O(m2n)
- 廣義表
結構體：struct node { int sz; //以目前結點的前驅結點為字首的向量個數 linklist *head; //存相同字首的目前次元結點連結清單 };每次插入一組向量是一個遞歸的過程，插入時候去搜尋目前次元相同的值的結點，如果發現不存在我現在要插入的結點，就直接插入該連結清單即可，目前結點的長度+1，要把更新的資訊傳回去，更新前繼結點的個數+1（相當于多了一條路徑）。這樣表頭的sz個數即整體的向量分類數
複雜度：每次查找目前次元不同值的複雜度是 O ( m ) O(m) O(m)，每次插入遞歸的深度最多是 O ( n ) O(n) O(n)，有m條向量要插入是以總複雜度也是 O ( m 2 n ) O(m^2n) O(m2n)。不過不難發現，每一層的查詢時間可以用一個哈希表把理論時間降到 O ( 1 ) O(1) O(1)，總複雜度可以降到 O ( n ∗ m ) O(n*m) O(n∗m)，但考慮到執行不同情況的穩定性用紅黑樹使複雜度變成 O ( n m l o g ( m ) ) O(nmlog(m)) O(nmlog(m))，并且可以利用STL的map也友善實作。
書中給的解法筆記
文中說複雜度是 O ( n 2 m ) O(n^2m) O(n2m)，不過可能是我沒了解它的算法精髓，故這裡隻是貼一下文中的方法，并加上自己對這個算法的了解：
主函數：
分别是讀入，分類以及輸出答案并釋放空間
1,讀入：
将m個n維向量存到一個二維數組vect[m][n]中；ind相當于一開始每個向量都屬于自己，類似于并查集的初始化；classind[m][2]的第一個表示所在類的開始位置，第二個表示所在類結束的位置，是以初始化結束的位置是m-1，相當于假設隻有一類，之後的算法就一直分割
2,第column維的分類：
每次把該列的相同的數交換到一塊，我們可以這樣想，用ind表示一個向量分類完所屬的位置，然後每次用雙指針維護，完成一次分類後會發現和第一個向量在該列相同的向量分别歸到前幾行，由于ind的原因，在邏輯上的可能分為一類的第一種向量已經歸為一類了
3,對目前已有的cnt個類對下一維再進行分類，傳回值為新增了多少類
關于該函數的詳細解釋：
index表示目前已經有的類，column表示要劃分的次元
classind可以馬上得出要進一步進行劃分的區間，因為ind已經使得前 c o l u m n − 1 column-1 column−1維的向量邏輯上相鄰了
cnt表示目前已有的類數量-1，因為把x-1類分完剩餘的一個類邏輯上也分完最終答案是cnt+1個類
cc表示細分之前分成一類的相鄰又多出來的類數
c表示每細分一種類多出來的數量，是以cc+=c-1相當于如果還是隻有1類那麼就沒新增，接着進入下一個類的劃分
4,疊代已分類完成的後幾維進行劃分，由于初始化的原因，剛開始預設劃分為一類：
實作
根據分類的算法寫的版本：
#include <bits/stdc++.h>
using namespace std;
const int N=100;
const int M=100;
int l[M], r[M]; //某一類邏輯上劃分完成後的左右區間，也就是最終這個區間内向量屬于一類
int ind[M]; //表示一個目前的位置
int vect[M][N], m, n; //存m個n維向量
void init() {
cin >> m >> n;
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
cin >> vect[i][j];
for(int i=0; i<m; i++) //每個向量一開始的位置不變
ind[i]=i;
l[0]=0; r[0]=m-1; //一開始隻有一個類區間為[0, m-1]
}
//把和[left, right]區間的以left的第col列相同一類分到一塊,并傳回這個類的右區間标記
int merge(int left, int right, int col) {
int val=vect[ind[left++]][col]; //用ind代表left這個位置的向量
while(left <= right) {
while(left <= right && vect[ind[left]][col] == val) left++; //找到第一個不等于val的向量
while(left <= right && vect[ind[right]][col] != val) right--; //找到最後一個和val同類的向量
if(left < right) {
swap(ind[left], ind[right]);
right--;
left++;
}
}
return left; //和二分中upper類似
}
//目前cnt+1個向量以第col維進行再劃分，傳回增加的種類數
int split(int cnt, int col) {
int now_add=0; //cnt個類劃分後新形成的類數
for(int i=0; i<=cnt; i++) {
int left=l[i], right=r[i]; //第i個類所在的區間
int cur_classfiy_sz=0; //第i個類通過col維能夠分成的區間個數
while(left<=right) {
int pre_left = left; //之前的右區間
if(cur_classfiy_sz == 1) r[i] = left-1; //更新第一個區間
left=merge(left, right, col); //将新區間的某個類劃分好(放到前面,并傳回下一個區間的開始)
cur_classfiy_sz++; //在目前類的區間又新劃分了一個類
if(cur_classfiy_sz > 1) {
l[cnt + now_add + cur_classfiy_sz - 1] = pre_left; //新找到一個類更新
r[cnt + now_add + cur_classfiy_sz - 1] = left - 1; //新的右區間
//這幾個資料的意思 cnt+now_add表示得到之前的類劃分的表尾，再偏移本輪之前找到的新類cur_classfiy-1
}
}
now_add += cur_classfiy_sz-1; //因為每一輪至少都有一個類，但不一定增加
}
return now_add;
}
//對已有的1個類進行再劃分，傳回劃分後的類數
int classfiy() {
int cnt=0; //一開始有沒有新的類
for(int i=0; i<n; i++)
cnt += split(cnt, i); //對每一維已有的類進行再劃分 預設有一個類
return cnt+1; //找到cnt個新類，共cnt+1個類
}
//對劃分後的每個類的樣子輸出
void output(int cnt) {
bool vis[M];
memset(vis, false, sizeof(vis));
cout << "\n共劃分為" << cnt << "個類，分别如下:\n" << endl;
for(int i=0; i<cnt-1; i++) {
cout << "第" << i+1 << "個類為:" << endl;
for(int j=l[i]; j<=r[i]; j++) {
vis[j] = true;
for(int z=0; z<n; z++)
cout << vect[ind[j]][z] << " ";
cout << "原位置 : " << ind[j] << " 現位置 : " << j << endl;
}
cout << endl;
}
cout << "第" << cnt << "個類為:" << endl;
for(int i=0; i<m; i++)
if(!vis[i]) {
vis[i] = true;
for(int j=0; j<n; j++)
cout << vect[ind[i]][j] << " ";
cout << "原位置 : " << ind[i] << " 現位置 : " << i << endl;
}
cout << "以上為" << cnt << "個類的劃分情況" << endl;
}
int main() {
init(); //初始化及輸入
output(classfiy()); //對m個n維向量分類并輸出
return 0;
}
/*
6 4
3 5 7 9
4 3 7 5
3 5 7 9
2 1 4 6
3 5 7 9
2 1 4 6
*/
/*
10 4
3 5 7 9
4 3 7 5
3 5 7 9
2 1 4 6
2 1 6 6
3 5 7 9
2 1 4 6
3 7 7 9
4 6 3 3
1 1 4 6
*/
/*
10 4
3 5 7 9
3 5 7 9
3 5 7 9
3 5 7 9
3 5 7 9
3 5 7 9
3 5 7 9
3 5 7 9
3 5 7 9
3 5 7 9
*/
/*
4 3
1 2 3
4 5 6
7 8 9
10 11 12
*/
效果展示
效果展示:
總結
這個算法根據不同類地劃分再進行更深層次地進一步劃分，有種分治的意味。