我正在创建一个最大3D年轻表，因此int[0][0][0]将具有表中最大的整数。所有行、列和窗格都按降序排列。我正试图为此创建maxify方法，但效果不太好。我试着从这里修改年轻人的方法，这就是我目前所拥有的：
private void maxify(int i, int j, int k) {
int largex = 0, largey = 0, largez = 0, x = 0, y = 0, z = 0;
while (true) {
x = largex;
y = largey;
z = largez;
if (x + 1 > i && x + 1 < tableau.length && tableau[x + 1][y][z] > tableau[x][y][z]) {
largex = x + 1;
largey = y;
largez = z;
}
if (y + 1 > j && y + 1 < tableau[0].length
&& tableau[x][y + 1][z] > tableau[largex][largey][largez]) {
largex = x;
largey = y + 1;
largez = z;
}
if (z + 1 > k && z + 1 < tableau[0][0].length
&& tableau[x][y][z + 1] > tableau[largex][largey][largez]) {
largex = x;
largey = y;
largez = z + 1;
}
if (largex != x || largey != y || largez != z) {
tableau[x][y][z] = tableau[x][y][z] ^ tableau[largex][largey][largez];
tableau[largex][largey][largez] = tableau[x][y][z]
^ tableau[largex][largey][largez];
tableau[x][y][z] = tableau[x][y][z] ^ tableau[largex][largey][largez];
maxify(largex, largey, largez);
} else
break;
}
}
以下是在3x3x1数组上调用时发生的情况的示例。
Starting with this array:
123
456
789
After first loop:
423
156
789
And so on....
423
156
789
423
756
189
423
756
189
423
756
819
423
756
819
423
756
891
423
756
891
423
756
891
成品阵列：
423
756
891
根本没有完全排序。有人能看到我在这件事上遗漏了什么吗？
原来的youngify()方法实际上并没有对整个二维数组进行排序！问题是，在检测到要进行的交换后，比如在第二行，下一次迭代从交换发生的地方开始(即从第二行开始(，而不考虑第一行元素上可能需要的其他交换，但在其他维度上。换句话说，它首先垂直地然后水平地筛选第一个元素。
这就是程序输出所显示的：1垂直移动，与4和7交换，然后水平移动，与8和9交换。总之，youngify()方法正确地向下筛选左上角的元素，而不考虑数组的其余部分。尝试使用{{9, 8, 7}, {6, 5, 4}, {3, 2, 1}}数组的原始youngify()方法，您会发现其行为完全相同。
反复筛选左上角的元素会起作用吗？不一定：如果最高元素已经在左上角的位置，则根本不会对任何元素进行[进一步]排序。
我建议对每个维度的多维数组按"行"进行排序。我写了以下代码：
private static void maxify(int[][][] tableau) {
int ii = tableau.length;
int jj = tableau[0].length;
int kk = tableau[0][0].length;
// Sort on k-rows
for (int i = 0; i < ii; i++) {
for (int j = 0; j < jj; j++) {
// Since k-rows are already standard arrays, no temporary array needed here.
reverseSort(tableau[i][j]);
}
}
// Sort on j-rows
for (int i = 0; i < ii; i++) {
for (int k = 0; k < kk; k++) {
int[] temp = new int[jj];
for (int j = 0; j < jj; j++) {
temp[j] = tableau[i][j][k];
}
reverseSort(temp);
for (int j = 0; j < jj; j++) {
tableau[i][j][k] = temp[j];
}
}
}
// Sort on i-rows
for (int j = 0; j < jj; j++) {
for (int k = 0; k < kk; k++) {
int[] temp = new int[ii];
for (int i = 0; i < ii; i++) {
temp[i] = tableau[i][j][k];
}
reverseSort(temp);
for (int i = 0; i < ii; i++) {
tableau[i][j][k] = temp[i];
}
}
}
}
private static void reverseSort(int[] a) {
Arrays.sort(a);
for (int i = 0; i < a.length / 2; i++) {
a[i] ^= a[a.length - i - 1];
a[a.length - i - 1] ^= a[i];
a[i] ^= a[a.length - i - 1];
}
}
我希望这会有所帮助。。。
干杯，
Jeff
private void tableau_heapify(int r, int c) {
int[] left = this.getLeft(r, c);
int[] right = this.getRight(r, c);
int[] smallest = new int[]{r, c};
// System.out.println(r + ", " + c);
//check if the cell is less than both of its children
if (this.isCellValid(left) && this.matrix[left[0]][left[1]] < this.matrix[r][c]) {
//save address of left cell
smallest = left;
}
if (this.isCellValid(right) && this.matrix[right[0]][right[1]] < this.matrix[smallest[0]][smallest[1]]) {
//save address of right cell
smallest = right;
}
//Check if we found changed address in our smallest variables.
//If yes, swap them. And, recursively call this method on that cell address
if (this.isCellValid(smallest) && (smallest[0] != r || smallest[1] != c)) {
//swap
int t = this.matrix[r][c];
this.matrix[r][c] = this.matrix[smallest[0]][smallest[1]];
this.matrix[smallest[0]][smallest[1]] = t;
// recursive call tableau_heapify
this.tableau_heapify(smallest[0], smallest[1]);
}
}
我在这里找到了这个cormen问题的最佳解释：Young Tableau