Dada una array mat[ ][ ] de tamaño N*N y un entero K , que contiene valores enteros, la tarea es reemplazar los elementos diagonales por el K-ésimo elemento más pequeño de la fila.
Ejemplos:
Entrada: mat[][]= {{1, 2, 3, 4}
{4, 2, 7, 6}
{3, 5, 1, 9}
{2, 4, 6, 8}}
K = 2
Salida : 2, 2, 3, 4
4, 4, 7, 6
3, 5, 3, 8
2, 4, 6, 4
Explicación: el segundo elemento más pequeño de la primera fila = 2
El segundo elemento más pequeño de la segunda fila es 4
El segundo elemento más pequeño de la 3.ª fila es 3.
El 2.º elemento más pequeño de la 4.ª fila es 4.Entrada: mat[][] = {{1, 2, 3}
{7, 9, 8}
{2, 3, 6}}
K = 2
Salida: 2, 2, 3
7, 8, 8
2, 3, 3
Enfoque: La solución se basa en el concepto de clasificación . Siga los pasos que se mencionan a continuación:
- Atraviesa la array por filas.
- Copie esta fila en otra lista.
- Ordene la lista y obtenga el K-ésimo elemento más pequeño y reemplace el elemento diagonal con eso.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
const int N = 4;
// Function to print Matrix
void showMatrix(int mat[][N])
{
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
}
// Function to return k'th smallest element
// in a given array
int kthSmallest(int arr[], int n, int K)
{
// Sort the given array
sort(arr, arr + n);
// Return k'th element
// in the sorted array
return arr[K - 1];
}
// Function to replace diagonal elements
// with Kth min element of row.
void ReplaceDiagonal(int mat[][N], int K)
{
int i, j;
int arr[N];
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
arr[j] = mat[i][j];
mat[i][i] = kthSmallest(arr, N, K);
}
showMatrix(mat);
}
// Utility Main function.
int main()
{
int mat[][N] = { { 1, 2, 3, 4 },
{ 4, 2, 7, 6 },
{ 3, 5, 1, 9 },
{ 2, 4, 6, 8 } };
int K = 3;
ReplaceDiagonal(mat, K);
return 0;
}
Java
// Java code to find the maximum median
// of a sub array having length at least K.
import java.util.*;
public class GFG
{
static int N = 4;
// Function to print Matrix
static void showMatrix(int mat[][])
{
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
System.out.print(mat[i][j] + " ");
}
System.out.println();
}
}
// Function to return k'th smallest element
// in a given array
static int kthSmallest(int arr[], int n, int K)
{
// Sort the given array
Arrays.sort(arr);
// Return k'th element
// in the sorted array
return arr[K - 1];
}
// Function to replace diagonal elements
// with Kth min element of row.
static void ReplaceDiagonal(int mat[][], int K)
{
int i, j;
int arr[] = new int[N];
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
arr[j] = mat[i][j];
mat[i][i] = kthSmallest(arr, N, K);
}
showMatrix(mat);
}
// Driver code
public static void main(String args[])
{
int mat[][] = { { 1, 2, 3, 4 },
{ 4, 2, 7, 6 },
{ 3, 5, 1, 9 },
{ 2, 4, 6, 8 } };
int K = 3;
ReplaceDiagonal(mat, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python code for the above approach
N = 4
# Function to print Matrix
def showMatrix(mat):
i = None
j = None
for i in range(N):
for j in range(N):
print(mat[i][j], end= " ")
print('')
# Function to return k'th smallest element
# in a given array
def kthSmallest(arr, n, K):
# Sort the given array
arr.sort()
# Return k'th element
# in the sorted array
return arr[K - 1]
# Function to replace diagonal elements
# with Kth min element of row.
def ReplaceDiagonal(mat, K):
i = None
j = None
arr = [0] * N
for i in range(N):
for j in range(N):
arr[j] = mat[i][j]
mat[i][i] = kthSmallest(arr, N, K)
showMatrix(mat)
# Utility Main function.
mat = [[1, 2, 3, 4], [4, 2, 7, 6], [3, 5, 1, 9], [2, 4, 6, 8]]
K = 3
ReplaceDiagonal(mat, K)
# This code is contributed by Saurabh Jaiswal
C#
// C# code to find the maximum median
// of a sub array having length at least K.
using System;
public class GFG {
static int N = 4;
// Function to print Matrix
static void showMatrix(int[, ] mat)
{
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
Console.Write(mat[i, j] + " ");
}
Console.WriteLine();
}
}
// Function to return k'th smallest element
// in a given array
static int kthSmallest(int[] arr, int n, int K)
{
// Sort the given array
Array.Sort(arr);
// Return k'th element
// in the sorted array
return arr[K - 1];
}
// Function to replace diagonal elements
// with Kth min element of row.
static void ReplaceDiagonal(int[, ] mat, int K)
{
int i, j;
int[] arr = new int[N];
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
arr[j] = mat[i, j];
mat[i, i] = kthSmallest(arr, N, K);
}
showMatrix(mat);
}
// Driver code
public static void Main()
{
int[, ] mat = { { 1, 2, 3, 4 },
{ 4, 2, 7, 6 },
{ 3, 5, 1, 9 },
{ 2, 4, 6, 8 } };
int K = 3;
ReplaceDiagonal(mat, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
let N = 4;
// Function to print Matrix
function showMatrix(mat) {
let i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
document.write(mat[i][j] + " ");
}
document.write('<br>')
}
}
// Function to return k'th smallest element
// in a given array
function kthSmallest(arr, n, K)
{
// Sort the given array
arr.sort(function (a, b) { return a - b })
// Return k'th element
// in the sorted array
return arr[K - 1];
}
// Function to replace diagonal elements
// with Kth min element of row.
function ReplaceDiagonal(mat, K)
{
let i, j;
let arr = new Array(N);
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
arr[j] = mat[i][j];
mat[i][i] = kthSmallest(arr, N, K);
}
showMatrix(mat);
}
// Utility Main function.
let mat = [[1, 2, 3, 4],
[4, 2, 7, 6],
[3, 5, 1, 9],
[2, 4, 6, 8]];
let K = 3;
ReplaceDiagonal(mat, K);
// This code is contributed by Potta Lokesh
</script>
3 2 3 4 4 6 7 6 3 5 5 9 2 4 6 6
Complejidad de Tiempo: O(N 2 * logN)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA