algorithm - 如何对数字数组进行排序以形成分散的数字？

Question

<分区>

Answer 1

好的。解决这个问题花了很长时间。

这是一个方法。虽然这个问题可能有多种技术，但我认为这个解决方案很容易理解。

1. 将所有元素排序到另一个数组中。
2. 定义 r = 0, c = 0。

3. 从数组中选取每个元素，然后尝试将其放入矩阵中。如果不可能，则尝试下一个位置。

   int n = matrix.size();
   int m = matrix[0].size();
   
   vector<int> arr;
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < m; j++) {
           arr.push_back(matrix[i][j]);
       }
   }
   sort(arr.begin(), arr.end());
   int dr[] = {-1, 0, 1, 0}; /// 4 sides
   int dc[] = {0, 1, 0, -1}; /// 4 sides
   int r = 0, c = 0;
   int new_matrix[n][m];
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < m; j++)
           new_matrix[i][j] = -1;
   }
   bool vis[n][m] = {false};
   for(int k = 0; k < n*m; ) {
       int cur_num = arr[k];
       bool check = false;
       if(!vis[r][c]) {
           for(int p = 0; p < 4; p++) {
               int adjr = r + dr[p];
               int adjc = c + dc[p];
               if(adjr < 0 || adjr >= n || adjc < 0 || adjc >= m) continue;
               if(new_matrix[adjr][adjc] == cur_num) check = true;
           }
           if(check == false) {
               new_matrix[r][c] = cur_num;
               vis[r][c] = true;
               k++;
           }
       }
       c++;
       if(c >= m) r++, c = c % m;
       if(r >= n) r = r % n;
   }
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < m; j++) {
           cout<<new_matrix[i][j]<<" ";
       }
       cout<<endl;
   }
   

编码愉快!!!