矩阵行中较大的值

Question

如何获得矩阵行中两个较大的数字？

如果矩阵中其他行的数字较大，则无法显示。

例如，假设我有以下矩阵，

int mat[][] ={{1,2,3}{4,5,6}{7,8,9}};

如果我从第 0 行搜索 2 个较大的数字，它应该返回索引 1 和 2（值 2 和 3）。

Answer 1

由于“矩阵”在 Java 中存储为数组数组的方式，问题简化为简单地在 int[] 中查找最高 2 个元素（可能具有相等值）的索引。

因此，解决方案非常简单：

public class Max2 { 
    static int[] max2(int... nums) {
        int high1v = Integer.MIN_VALUE;
        int high2v = Integer.MIN_VALUE;
        int high1i = -1;
        int high2i = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= high1v) {
                high2v = high1v;
                high2i = high1i;
                high1v = nums[i];
                high1i = i;
            } else if (nums[i] >= high2v) {
                high2v = nums[i];
                high2i = i;
            }
        }
        return new int[] { high1i, high2i };
    }
}

使用数组的 1 遍 O(N) 线性扫描。 Integer.MIN_VALUE 和 >= 比较的组合使其一切正常。 high1i 是第一个最高元素的索引，high2v 是第二个最高元素的值，依此类推。

static void print(int[] arr) {
    System.out.println(java.util.Arrays.toString(arr));
}
public static void main(String[] args) {
    int[][] matrix = {
        { 1,2,3 }, // [2, 1]
        { 6,5,4 }, // [0, 1]
        { 8,7,9 }, // [2, 0]
        { 0,0,0 }, // [2, 1]
    };

    // print the indices of the maximum 2 elements in each row
    for (int[] row : matrix) {
        print(max2(row));
    }

    print(max2(matrix[1]));
    // matrix[1] is the { 6, 5, 4 } row; prints "[0, 1]"

    print(max2(Integer.MIN_VALUE, Integer.MIN_VALUE));
    // works with varargs, and Integer.MIN_VALUE as real values
}

Answer 2

更新以返回索引。另外，我认为在此过程中更改原始矩阵是不可取的，因此我编写了一个测试来确认我的原始实现确实更改了矩阵，然后修改了代码，使其不再更改。

package playground.tests;

import java.util.Arrays;

import junit.framework.TestCase;

public class BiggerTest extends TestCase {

    public void testBigger() throws Exception {
        int mat[][] = { { 3, 1, 2 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[] result = bigger(0, 2, mat);
        assertEqualArrays(new int[] { 2, 3 }, result);
    }

    public void testBiggerDoesntChangeOriginalMatrix() throws Exception {
        int mat[][] = { { 3, 1, 2 }, { 4, 5, 6 }, { 7, 8, 9 } };
        bigger(0, 2, mat);
        assertEqualArrays(new int[] { 3, 1, 2 }, mat[0]);
    }

    public void testBiggerIndex() throws Exception {
        int mat[][] = { { 3, 1, 2 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[] result = biggerIndexes(0, 2, mat);
        assertEqualArrays(new int[] { 2, 0 }, result);
    }

    private int[] biggerIndexes(int rowIndex, int count, int[][] matrix) {
        int[] biggerValues = bigger(rowIndex, count, matrix);
        int[] row = matrix[rowIndex];
        int[] result = new int[count];
        for (int i = 0; i < result.length; i++) 
            result[i] = findIndex(biggerValues[i], row);
        return result;
    }

    private int findIndex(int value, int[] values) {
        for (int i = 0; i < values.length; i++) 
            if (values[i] == value)
                return i;
        return -1;
    }

    private int[] bigger(int rowIndex, int count, int[][] matrix) {
        int[] row = copy(matrix[rowIndex]);
        Arrays.sort(row);
        int[] result = new int[count];
        for (int i = 0; i < count; i++)
            result[i] = row[i + row.length - count];
        return result;
    }

    private static int[] copy(int[] original) {
        int[] result = new int[original.length];
        for (int i = 0; i < result.length; i++) 
            result[i] = original[i];
        return result;
    }

    private static void assertEqualArrays(int[] a, int[] b) {
        assertEquals(a.length, b.length);
        for (int i = 0; i < a.length; i++)
            assertEquals(a[i], b[i]);
    }
}

Answer 3

我对 @Carl 代码进行了改编，我得到了这个，

private int[] bigger(int rowIndex, int count, int[][] matrix) {
    int[] row = matrix[rowIndex];
    int[] original = matrix[rowIndex];
    int[] result = new int[count];

    Arrays.sort(row);

    for (int i = 0; i < count; i++){
        for(int j = 0; j < original.length; j++){
            if(row[row.length - 1 - i] == original[j]){
                result[i] = j;
                original[j] = Integer.MIN_VALUE;
                // break;
            }
        }
    }
    return result;
}

我们可以在我评论的地方放置一个 break 指令，但我不知道它是否会提高算法的性能。