Чем больше значение в строке матрицы

Question

Как я могу получить 2 больших числа строки матрицы?

Если матрица имеет большее число в другой строке, она не может быть показана.

Например, предположим, у меня есть следующая матрица

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

если я найду 2 больших числа из строки 0, он должен вернуть мне индексы 1 и 2 (значения 2 и 3).

Answer 1

Из-за того, как ваша «матрица» хранится в Java в виде массива массивов, проблема сводится к простому нахождению индексов двух старших элементов (возможно, равных значений) в int[].

Решение, таким образом, довольно простое:

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 , где я прокомментировал, но я не знаю, улучшит ли она производительность алгоритма.