如果有個2維資料範圍很大, ,x介於1到30000, y介於-30000到30000, 但是(x,y)的資料量不多, 最多250000筆. 這時通常不會開個xy[30001][60001]陣列來存資料, 而是放在xy[250000][3].
問題來了,如果要在xy[250000][3]裡快速地尋找同樣x或是同樣y的資料,要怎麼做呢?
我利用set來記錄資料順序, 因為資料不會重複而且set會自動幫我排序. SetX[30001]用y排序, SetY[60001]用x排序. 資料輸入後, 其實就已經排好了.
#include <stdio.h>
#include <memory.h>
#include <set>
#include<iostream>
using namespace std;
class XYNode{
public:
int X;
int Y;
int DATA;
void Set(int x, int y, int data){
X=x;
Y=y;
DATA=data;
}
};
XYNode xynode[250000];
int NodeSize=0;
class CompareX{
public:
bool operator()(XYNode const *a, XYNode const *b) const {
return a->X<b->X;
}
};
class CompareY{
public:
bool operator()(XYNode const *a, XYNode const *b) const {
return a->Y<b->Y;
}
};
set<XYNode*, CompareX> SetY[60001];
set<XYNode*, CompareY> SetX[30001];
int main()
{
//輸入資料
int loop;
cin >> loop;
int x,y,data;
while(loop--){
cin >> x >> y >> data;
xynode[NodeSize].Set(x,y,data);
SetY[y+30000].insert(&xynode[NodeSize]);
SetX[x].insert(&xynode[NodeSize]);
NodeSize++;
}
cout << endl;
cout << endl;
//列印資料
for(y=30000;y>=-30000;y--){
if(!SetY[y+30000].empty()){
cout << "Y="<<y<<" ";
auto it = SetY[y+30000].begin();
while(it != SetY[y+30000].end()){
cout << " " << (*it)->X <<":"<< (*it)->DATA;
it++;
}
cout << endl;
}
}
return 0;
}
測試資料
輸入一個正整數 N(1≤N≤250000)，代表DATA的數量，接下來有N行，每一行有三個數字 X,Y和DATA。
10
2 0 1
2 -1 1
7 -1 0
7 2 1
4 2 0
4 1 0
3 1 1
3 2 0
1 -1 1
1 4 0
輸出結果
每列Y從大到小排序輸出, 同一列X從小到大排序。
Y=4 1:0
Y=2 3:0 4:0 7:1
Y=1 3:1 4:0
Y=0 2:1
Y=-1 1:1 2:1 7:0
