提取和排序數組中的數據？

Question

這裏是我的數組：

int grid[gridsize+1] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 3, 3, 3, 2, 2, 4, 1, 5, 3, 3, 6, 2, 6, 4, 5, 5, 5, 3, 6, 2, 6, 4, 4, 5, 5, 5, 6, 6, 6, 4, 7, 7, 8, 5, 8, 8, 8, 4, 7, 7, 8, 8, 8, 8, 8, 4, 7, 7, 7, 7, 8, 8, 8 }; 

每個數字代表一種顏色，我想每一個唯一的編號創建多個磁盤陣列。創建的數組將從原始數組中存儲該數字的位置。

e.g

colour1[5] 
[0]=0  //because the number 1 is stored in element 0. 
[1]=1 
[2]=8 
[3]=9 

電網將改變我每次運行時的數字，這樣的事情必須是動態的？ 我可以編寫低效率的代碼來完成這個任務，但它只是重複性的，我無法理解一種方法將它變成我可以放入函數中的東西。

這是我的;

int target_number = 1 
grid_size = 64; 
int counter = -1; 
int counter_2 = -1; 
int colour_1; 
while (counter < grid_size + 1){ 
    counter = counter + 1; 
    if (grid[counter] == target) 
     counter_2 = counter_2 + 1; 
     colour_1[counter_2] = counter; 
    } 
} 

我必須爲每種顏色做到這一點，當我試圖做一個功能，在主讓沒用它無法訪問主陣列。

Answer 1

您可以使用vector<vector<int>>來表示您的計數器。沒有地圖或排序是必要的。

編輯：添加額外的通過來確定最大的顏色，所以不需要運行時調整大小。

下面是代碼：

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main() { 
    int grid[] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 3, /*...*/}; 
    const size_t gridSize = std::end(grid) - std::begin(grid); 
    int maxColor = *std::max_element(std::begin(grid), std::end(grid)); 
    std::vector<std::vector<int>> colorPos(maxColor); 

    for (size_t i = 0; i < gridSize; ++i) 
     colorPos[grid[i] - 1].push_back(i); 

    for (size_t i = 0; i < colorPos.size(); ++i) { 
     std::cout << (i + 1) << ": "; 
     for (int p : colorPos[i]) 
      std::cout << p << ' '; 
     std::cout << std::endl; 
    } 

    return 0; 
} 

輸出：

1: 0 1 8 9 10 17 
2: 2 3 4 5 6 7 14 15 22 30 
3: 11 12 13 19 20 28 
4: 16 24 32 33 40 48 56 
5: 18 25 26 27 34 35 36 44 
6: 21 23 29 31 37 38 39 
7: 41 42 49 50 57 58 59 60 
8: 43 45 46 47 51 52 53 54 55 61 62 63 

Answer 2

也許最好使用一些關聯容器，例如std::unordered_map或std::multimap。

下面是一個示範程序

#include <iostream> 
#include <map> 

int main() 
{ 
    int grid[] = 
    { 
     1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 3, 3, 3, 2, 2, 
     4, 1, 5, 3, 3, 6, 2, 6, 4, 5, 5, 5, 3, 6, 2, 6, 
     4, 4, 5, 5, 5, 6, 6, 6, 4, 7, 7, 8, 5, 8, 8, 8, 
     4, 7, 7, 8, 8, 8, 8, 8, 4, 7, 7, 7, 7, 8, 8, 8 
    }; 

    std::multimap<int, int> m; 

    int i = 0; 
    for (int x : grid) 
    { 
     m.insert({ x, i++ }); 
    } 

    std::multimap<int, int>::size_type n = m.count(1); 
    std::cout << "There are " << n << " elements of color 1:"; 

    auto p = m.equal_range(1); 

    for (; p.first != p.second ; ++p.first) 
    { 
     std::cout << ' ' << p.first->second; 
    } 

    std::cout << std::endl; 

    return 0; 
} 

輸出

There are 6 elements of color 1: 0 1 8 9 10 17 

或者

#include <iostream> 
#include <map> 

int main() 
{ 
    int grid[] = 
    { 
     1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 3, 3, 3, 2, 2, 
     4, 1, 5, 3, 3, 6, 2, 6, 4, 5, 5, 5, 3, 6, 2, 6, 
     4, 4, 5, 5, 5, 6, 6, 6, 4, 7, 7, 8, 5, 8, 8, 8, 
     4, 7, 7, 8, 8, 8, 8, 8, 4, 7, 7, 7, 7, 8, 8, 8 
    }; 

    std::multimap<int, int> m; 

    int i = 0; 
    for (int x : grid) 
    { 
     m.insert({ x, i++ }); 
    } 

    for (auto first = m.begin(); first != m.end();) 
    { 
     auto n = m.count(first->first); 
     std::cout << "There are " << n 
        << " elements of color " << first->first << ":"; 

     auto p = m.equal_range(first->first); 

     for (; p.first != p.second ; ++p.first) 
     { 
      std::cout << ' ' << p.first->second; 
     } 

     std::cout << std::endl; 

     first = p.first; 
    } 

    return 0; 
} 

輸出是

There are 6 elements of color 1: 0 1 8 9 10 17 
There are 10 elements of color 2: 2 3 4 5 6 7 14 15 22 30 
There are 6 elements of color 3: 11 12 13 19 20 28 
There are 7 elements of color 4: 16 24 32 33 40 48 56 
There are 8 elements of color 5: 18 25 26 27 34 35 36 44 
There are 7 elements of color 6: 21 23 29 31 37 38 39 
There are 8 elements of color 7: 41 42 49 50 57 58 59 60 
There are 12 elements of color 8: 43 45 46 47 51 52 53 54 55 61 62 63 

Answer 3

我認爲你最好使用計數排序，這是一種排序算法，非常適合用於排序具有多個重複值比O（n log n）時間更好的大型簡單類型組。下面是一些示例代碼，有註釋爲清楚：

// set up our grid 
int grid_raw[] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 3, 3, 3, 2, 2, 4, 1, 5, 3, 3, 6, 2, 6, 4, 5, 5, 5, 3, 6, 2, 6, 4, 4, 5, 5, 5, 6, 6, 6, 4, 7, 7, 8, 5, 8, 8, 8, 4, 7, 7, 8, 8, 8, 8, 8, 4, 7, 7, 7, 7, 8, 8, 8}; 

// build a vector using our raw list of numbers. This calls the range constructor: 
// (number 3) http://www.cplusplus.com/reference/vector/vector/vector/ 
// The trick to using sizeof is that I don't have to change anything if my grid's 
// size changes (sizeof grid_raw gives the number of bytes in the whole array, and 
// sizeof *grid_raw gives the number of bytes in one element, so dividing yields 
// the number of elements. 
std::vector<int> grid(grid_raw, grid_raw + sizeof grid_raw/sizeof *grid_raw); 

// count the number of each color. std::map is an associative, key --> value 
// container that's good for doing this even if you don't know how many colors 
// you have, or what the possible values are. Think of the values in grid as being 
// colors, not numbers, i.e. ++buckets[RED], ++buckets[GREEN], etc... 
// if no bucket exists for a particular color yet, then it starts at zero (i.e, 
// the first access of buckets[MAUVE] will be 0, but it remembers each increment) 
std::map<int, int> buckets; 
for (vector<int>::iterator i = grid.begin(); i != grid.end(); ++i) 
    ++buckets[*i]; 

// build a new sorted vector from buckets, which now contains a count of the number 
// of occurrences of each color. The list will be built in the order of elements 
// in buckets, which will default to the numerical order of the colors (but can 
// be customized if desired). 
vector<int> sorted; 
for (map<int, int>::iterator b = buckets.begin(); b != buckets.end(); ++b) 
    sorted.insert(sorted.end(), b->second, b->first); 

// at this point, sorted = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, ...} 

Read more about the Counting Sort (includes example python code)

這裏是一個ideone用於演示排序網格。

我不是100％確定這會回答你的問題......但是你包括了在標題中的排序，即使你沒有在你的問題的主體中提到它。

Answer 4

如果不強制使用普通的數組，我可以提出地圖上的顏色位置的向量：

• map是一個關聯容器，對任何顏色鍵返回一個引用
• 這裏使用的引用將是包含所有位置的vector（一種動態數組）。

你輸入網格包含顏色代碼：

typedef int colorcode; // For readability, to make diff between counts, offsets, and colorcodes 
colorcode grid[] = { 1, 1, /* .....input data as above.... */ ,8 }; 
const size_t gridsize = sizeof(grid)/sizeof(int); 

你可以這樣定義彩色地圖：

map<colorcode, vector<int>> colormap; 
//  ^^^ key  ^^^ value maintained for the key 

通過這種方法，您color1[..]然後將通過一個更加動態corlormap[1][..]取代。而且它很容易填寫：

for (int i = 0; i < gridsize; i++) 
    colormap[grid[i]].push_back(i); // add the new position to the vector returned for the colormap of the color 

要驗證的結果，您可以通過地圖迭代，併爲每個現有的值通過位置迭代：

for (auto x : colormap) {  // for each color in the map 
    cout << "Color" << x.first << " : "; // display the color (key) 
    for (auto y : x.second)  // and iterate through the vector of position 
     cout << y << " "; 
    cout << endl; 
} 

你不知道可以肯定你有多少種不同的顏色代碼，但是你想要存儲的代碼爲