Dada una array de enteros y un número K. La tarea es ordenar solo aquellos elementos de la array que producen el resto P al dividir por K. La clasificación debe hacerse en sus posiciones relativas solo sin afectar a ningún otro elemento.
Ejemplos :
Entrada : arr[] = {10, 3, 2, 6, 12}, K = 4, P = 2
Salida : 2 3 6 10 12
Entrada : arr[] = {3, 4, 5, 10, 11, 1 }, K = 3, P = 1
Salida : 3 1 5 4 11 10
Acercarse:
- Inicializar dos vectores vacíos .
- Recorra la array, de izquierda a derecha y verifique el módulo de cada elemento con K.
- En el primer vector, inserte el índice de todos los elementos que produce el resto P.
- En el segundo vector, inserte los elementos que producen el resto P.
- Ordenar el segundo vector.
- Ahora, tenemos el índice de todos los elementos requeridos y también todos los elementos requeridos en orden.
- Entonces, inserte los elementos del segundo vector en la array en los índices presentes en el primer vector uno por uno.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for sorting array elements
// whose modulo with K yields P
#include <bits/stdc++.h>
using namespace std;
// Function to sort elements
// whose modulo with K yields P
void sortWithRemainderP(int arr[], int n, int k, int p)
{
// initialise two vectors
vector<int> v1, v2;
for (int i = 0; i < n; i++) {
if (arr[i] % k == p) {
// first vector contains indices of
// required element
v1.push_back(i);
// second vector contains
// required elements
v2.push_back(arr[i]);
}
}
// sorting the elements in second vector
sort(v2.begin(), v2.end());
// replacing the elements whose modulo with K yields P
// with the sorted elements
for (int i = 0; i < v1.size(); i++)
arr[v1[i]] = v2[i];
// printing the new sorted array elements
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 8, 255, 16, 2, 4, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
int p = 0;
sortWithRemainderP(arr, n, k, p);
return 0;
}
Java
// Java program for sorting array elements
// whose modulo with K yields P
import java.util.*;
class GFG
{
// Function to sort elements
// whose modulo with K yields P
static void sortWithRemainderP(int arr[], int n, int k, int p)
{
// initialise two vectors
Vector<Integer> v1 = new Vector<Integer>();
Vector<Integer> v2 = new Vector<Integer>();
for (int i = 0; i < n; i++)
{
if (arr[i] % k == p)
{
// first vector contains indices of
// required element
v1.add(i);
// second vector contains
// required elements
v2.add(arr[i]);
}
}
// sorting the elements in second vector
Collections.sort(v2);
// replacing the elements whose modulo with K yields P
// with the sorted elements
for (int i = 0; i < v1.size(); i++)
arr[v1.get(i)] = v2.get(i);
// printing the new sorted array elements
for (int i = 0; i < n; i++)
System.out.print(arr[i]+" ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 8, 255, 16, 2, 4, 0 };
int n = arr.length;
int k = 2;
int p = 0;
sortWithRemainderP(arr, n, k, p);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for sorting array # elements whose modulo with K yields P # Function to sort elements whose modulo # with K yields P def sortWithRemainderP(arr, n, k, p): # initialise two vectors v1 = [] v2 = [] for i in range(0, n, 1): if (arr[i] % k == p): # first vector contains indices # of required element v1.append(i) # second vector contains # required elements v2.append(arr[i]) # sorting the elements in second vector v2.sort(reverse = False) # replacing the elements whose modulo # with K yields P with the sorted elements for i in range(0, len(v1), 1): arr[v1[i]] = v2[i] # printing the new sorted array elements for i in range(0, n, 1): print(arr[i], end = " ") # Driver code if __name__ == '__main__': arr = [8, 255, 16, 2, 4, 0] n = len(arr) k = 2 p = 0 sortWithRemainderP(arr, n, k, p) # This code is contributed by # Sahil_Shelangia
C#
// C# program for sorting array elements
// whose modulo with K yields P
using System;
using System.Collections.Generic;
class GFG
{
// Function to sort elements
// whose modulo with K yields P
static void sortWithRemainderP(int []arr, int n,
int k, int p)
{
// initialise two vectors
List<int> v1 = new List<int>();
List<int> v2 = new List<int>();
for (int i = 0; i < n; i++)
{
if (arr[i] % k == p)
{
// first vector contains indices of
// required element
v1.Add(i);
// second vector contains
// required elements
v2.Add(arr[i]);
}
}
// sorting the elements in second vector
v2.Sort();
// replacing the elements whose modulo with
// K yields P with the sorted elements
for (int i = 0; i < v1.Count; i++)
arr[v1[i]] = v2[i];
// printing the new sorted array elements
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 8, 255, 16, 2, 4, 0 };
int n = arr.Length;
int k = 2;
int p = 0;
sortWithRemainderP(arr, n, k, p);
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP program for sorting array elements
// whose modulo with K yields P
// Function to sort elements
// whose modulo with K yields P
function sortWithRemainderP($arr, $n, $k, $p)
{
// initialise two vectors
$v1 = array();
$v2 = array();
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] % $k == $p)
{
// first vector contains indices of
// required element
array_push($v1, $i);
// second vector contains
// required elements
array_push($v2, $arr[$i]);
}
}
// sorting the elements in second vector
sort($v2);
// replacing the elements whose modulo with K
// yields P with the sorted elements
for ($i = 0; $i < count($v1); $i++)
$arr[$v1[$i]] = $v2[$i];
// printing the new sorted array elements
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
}
// Driver code
$arr = array( 8, 255, 16, 2, 4, 0 );
$n = count($arr);
$k = 2;
$p = 0;
sortWithRemainderP($arr, $n, $k, $p);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program for sorting array elements
// whose modulo with K yields P
// Function to sort elements
// whose modulo with K yields P
function sortWithRemainderP(arr, n, k, p)
{
// initialise two vectors
var v1 = [], v2 = [];
for (var i = 0; i < n; i++) {
if (arr[i] % k == p) {
// first vector contains indices of
// required element
v1.push(i);
// second vector contains
// required elements
v2.push(arr[i]);
}
}
// sorting the elements in second vector
v2.sort((a,b)=> a-b)
// replacing the elements whose modulo with K yields P
// with the sorted elements
for (var i = 0; i < v1.length; i++)
arr[v1[i]] = v2[i];
// printing the new sorted array elements
for (var i = 0; i < n; i++)
document.write( arr[i] + " ");
}
// Driver code
var arr = [8, 255, 16, 2, 4, 0 ];
var n = arr.length;
var k = 2;
var p = 0;
sortWithRemainderP(arr, n, k, p);
</script>
Producción:
0 255 2 4 8 16
Complejidad de tiempo: O (nlogn)
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA