#Day57 из #100days_of_coding

Сегодня мой 57-й день кодинга. Сегодня решил 3 задачи.

Проблема 1: Медиана в массиве, отсортированном по строкам

Для заданной построчной сортировки матрицы размером R*C, где R и C всегда нечетны, найдите медиану матрицы.

Пример 1:

Input:
R = 3, C = 3
M = [[1, 3, 5], 
     [2, 6, 9], 
     [3, 6, 9]]
Output: 5
Explanation: Sorting matrix elements gives 
us {1,2,3,3,5,6,6,9,9}. Hence, 5 is median.

Пример 2:

Input:
R = 3, C = 1
M = [[1], [2], [3]]
Output: 2
Explanation: Sorting matrix elements gives 
us {1,2,3}. Hence, 2 is median.

Ваша задача:
вам не нужно ничего читать или печатать. Ваша задача — выполнить функцию median(), которая принимает целые числа R и C вместе с двумерной матрицей. в качестве входных параметров и возвращает медиану матрицы.

Ожидаемая временная сложность: O(32 * R * log(C))
Ожидаемое вспомогательное пространство:O(1)

Решение (в Java):

lass Solution {
    int median(int matrix[][], int R, int C) {
          
        List<Integer> l=new ArrayList<>();
        int m=0;
        for( int i=0; i<R; i++){
            for( int j=0; j<C; j++)
            l.add(matrix[i][j]);
        }
        Collections.sort(l);
        int n=l.size();
        if( n%2==1){
            m=l.get(((n+1)/2)-1);
        }
        else
        m=l.get((n/2)-1)+l.get((n/2)/2);
        
        
        return m;
    }
}

Проблема 2: Строка с максимальным числом секунд 1

Дан логический двумерный массив размером n x m, где каждая строка отсортирована. Найдите отсчитываемый от 0 индекс первой строки с максимальным количеством 1.

Пример 1:

Input: 
N = 4 , M = 4
Arr[][] = {{0, 1, 1, 1},
           {0, 0, 1, 1},
           {1, 1, 1, 1},
           {0, 0, 0, 0}}
Output: 2
Explanation: Row 2 contains 4 1's (0-based
indexing).

Пример 2:

Input: 
N = 2, M = 2
Arr[][] = {{0, 0}, {1, 1}}
Output: 1
Explanation: Row 1 contains 2 1's (0-based
indexing).

Ваша задача.
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию rowWithMax1s(), которая принимает в качестве входных параметров массив логических значений arr[][], n и m и возвращает отсчитываемый от 0 индекс первой строки с наибольшим количеством единиц. Если такой строки не существует, вернуть -1.

Ожидаемая временная сложность: O(N+M)
Ожидаемое вспомогательное пространство: O(1)

Решение (в Java):

class Solution {
    int rowWithMax1s(int arr[][], int n, int m) {
     
        int ans=0, max=-1;
        for( int i=0; i<n; i++){
            int count=0;
            for( int j=0; j<m; j++){
                if(arr[i][j]==1)
                count++;
            }
            if(count>ans){
                ans=count;
                max=i;
            }
            
        }
        return max;
    }
}

Проблема 3: Отсортированная матрица

Дана матрица NxN Матем. Отсортируйте все элементы матрицы.

Пример 1:

Input:
N=4
Mat=[[10,20,30,40],
[15,25,35,45] 
[27,29,37,48] 
[32,33,39,50]]
Output:
10 15 20 25 
27 29 30 32
33 35 37 39
40 45 48 50
Explanation:
Sorting the matrix gives this result.

Пример 2:

Input:
N=3
Mat=[[1,5,3],[2,8,7],[4,6,9]]
Output:
1 2 3 
4 5 6
7 8 9
Explanation:
Sorting the matrix gives this result.

Ваша задача
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию sortedMatrix(), которая принимает целое число N и матрицу Mat в качестве входных параметров и возвращает отсортированную матрицу.

Ожидаемая временная сложность: O(N2LogN)
Ожидаемое вспомогательное пространство:O(N2)

Решение (в Java):

class Solution {
    int[][] sortedMatrix(int N, int Mat[][]) {
      
      List<Integer> l= new ArrayList<>();
      for(int i=0; i<N; i++){
          for(int j=0;j<N; j++)
          l.add(Mat[i][j]);
      }
      Collections.sort(l);
      int k=0;
      for( int i=0;i<N; i++){
          for(int j=0; j<N; j++){
              Mat[i][j]=l.get(k++);
              
          }
      }
       return Mat;
       
    }
}