Dada una lista N , la tarea es ordenar todos los elementos en posiciones pares e impares en orden creciente. Después de ordenar, necesitamos juntar todos los elementos en posiciones impares, luego todos los elementos en posiciones pares.
Ejemplos:
Input : [3, 2, 7, 6, 8]
Output : 3 7 8 2 6
Explanation:
Odd position elements in sorted order are 3, 7, 8.
Even position elements in sorted order are 2, 6.
Input : [1, 0, 2, 7, 0, 0]
Output : 0 1 2 0 0 7
Odd {1, 2, 0}
Even {0, 7, 0}
Acercarse:
- Inicialice dos listas para almacenar los dígitos indexados pares e impares.
- Recorra todos los dígitos y almacene los dígitos indexados impares en la lista de índices impares y los dígitos indexados pares en la lista de índices pares .
- Imprime los elementos en la lista de índices impares en orden ordenado.
- Imprime los elementos en la lista even_indexes en orden ordenado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
// function to print the odd and even indexed digits
void odd_even(int arr[], int n)
{
// lists to store the odd and
// even positioned digits
vector<int> odd_indexes;
vector<int>even_indexes;
// traverse through all the indexes
// in the integer
for (int i = 0; i < n;i++)
{
// if the digit is in odd_index position
// append it to odd_position list
if (i % 2 == 0)
odd_indexes.push_back(arr[i]);
// else append it to the even_position list
else
even_indexes.push_back(arr[i]);
}
// print the elements in the list in sorted order
sort(odd_indexes.begin(), odd_indexes.end());
sort(even_indexes.begin(), even_indexes.end());
for(int i = 0; i < odd_indexes.size();i++)
cout << odd_indexes[i] << " ";
for(int i = 0; i < even_indexes.size(); i++)
cout << even_indexes[i] << " ";
}
// Driver code
int main()
{
int arr[] = {3, 2, 7, 6, 8};
int n = sizeof(arr)/sizeof(arr[0]);
odd_even(arr, n);
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// function to print the odd and even indexed digits
static void odd_even(int arr[], int n)
{
// lists to store the odd and
// even positioned digits
Vector<Integer> odd_indexes = new Vector<Integer>();
Vector<Integer> even_indexes = new Vector<Integer>();
// traverse through all the indexes
// in the integer
for (int i = 0; i < n;i++)
{
// if the digit is in odd_index position
// append it to odd_position list
if (i % 2 == 0)
odd_indexes.add(arr[i]);
// else append it to the even_position list
else
even_indexes.add(arr[i]);
}
// print the elements in the list in sorted order
Collections.sort(odd_indexes);
Collections.sort(even_indexes);
for(int i = 0; i < odd_indexes.size(); i++)
System.out.print(odd_indexes.get(i) + " ");
for(int i = 0; i < even_indexes.size(); i++)
System.out.print(even_indexes.get(i) + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = {3, 2, 7, 6, 8};
int n = arr.length;
odd_even(arr, n);
}
}
// This code is contributed by Rajput-Ji
Python3
# function to print the odd and even indexed digits def odd_even(n): # lists to store the odd and # even positioned digits odd_indexes = [] even_indexes = [] # traverse through all the indexes # in the integer for i in range(len(n)): # if the digit is in odd_index position # append it to odd_position list if i % 2 == 0: odd_indexes.append(n[i]) # else append it to the even_position list else: even_indexes.append(n[i]) # print the elements in the list in sorted order for i in sorted(odd_indexes): print(i, end =" ") for i in sorted(even_indexes): print(i, end =" ") # Driver Code n = [3, 2, 7, 6, 8] odd_even(n)
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// function to print the odd and even indexed digits
static void odd_even(int []arr, int n)
{
// lists to store the odd and
// even positioned digits
List<int> odd_indexes = new List<int>();
List<int> even_indexes = new List<int>();
// traverse through all the indexes
// in the integer
for (int i = 0; i < n;i++)
{
// if the digit is in odd_index position
// append it to odd_position list
if (i % 2 == 0)
odd_indexes.Add(arr[i]);
// else append it to the even_position list
else
even_indexes.Add(arr[i]);
}
// print the elements in the list in sorted order
odd_indexes.Sort();
even_indexes.Sort();
for(int i = 0; i < odd_indexes.Count; i++)
Console.Write(odd_indexes[i] + " ");
for(int i = 0; i < even_indexes.Count; i++)
Console.Write(even_indexes[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
int []arr = {3, 2, 7, 6, 8};
int n = arr.Length;
odd_even(arr, n);
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP implementation of above approach
// function to print the odd and even
// indexed digits
function odd_even($n)
{
// lists to store the odd and
// even positioned digits
$odd_indexes = array();
$even_indexes = array();
// traverse through all the indexes
// in the integer
for ($i = 0; $i < sizeof($n); $i++)
{
// if the digit is in odd_index position
// append it to odd_position list
if ($i % 2 == 0)
array_push($odd_indexes, $n[$i]);
// else append it to the even_position list
else
array_push($even_indexes, $n[$i]);
}
// print the elements in the list in sorted order
sort($odd_indexes);
for ($i = 0; $i < sizeof($odd_indexes); $i++)
echo $odd_indexes[$i], " ";
sort($even_indexes) ;
for ($i = 0; $i < sizeof($even_indexes); $i++)
echo $even_indexes[$i], " ";
}
// Driver Code
$n = array(3, 2, 7, 6, 8);
odd_even($n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of above approach
// function to print the odd and even indexed digits
function odd_even(arr, n)
{
// lists to store the odd and
// even positioned digits
var odd_indexes = [];
var even_indexes = [];
// traverse through all the indexes
// in the integer
for (var i = 0; i < n;i++)
{
// if the digit is in odd_index position
// append it to odd_position list
if (i % 2 == 0)
odd_indexes.push(arr[i]);
// else append it to the even_position list
else
even_indexes.push(arr[i]);
}
// print the elements in the list in sorted order
odd_indexes.sort();
even_indexes.sort();
for(var i = 0; i < odd_indexes.length;i++)
document.write( odd_indexes[i] + " ");
for(var i = 0; i < even_indexes.length; i++)
document.write( even_indexes[i] + " ");
}
// Driver code
var arr = [3, 2, 7, 6, 8];
var n = arr.length;
odd_even(arr, n);
</script>
Producción
3 7 8 2 6
Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(n)
Otro enfoque: el problema anterior también se puede resolver sin el uso del espacio auxiliar. La idea es intercambiar el elemento de posiciones pares de la primera mitad con el elemento de posiciones impares de la segunda mitad. De esta forma, todos los elementos colocados de forma extraña aparecerán en la primera mitad, mientras que todos los elementos colocados uniformemente aparecerán en la segunda mitad de la array. Después de hacer esto, ordenaremos la primera mitad y luego la segunda mitad de la array en orden creciente individualmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the odd and even indexed digits
void odd_even(int arr[], int n)
{
// First even position
// as the index starts from 0
int i = 1;
// Last index
int j = n - 1;
// If last position is even
if (j % 2 != 0)
// Decrement j to odd position
j--;
// Swapping till half of the array
// so that all odd positioned element
// will occur in first half and
// even positioned element will
// occur in second half.
while (i < j) {
swap(arr[i], arr[j]);
i += 2;
j -= 2;
}
// Sorting first half of the array
// containing odd positioned elements
// in increasing order
sort(arr, arr + (n + 1) / 2);
// Sorting second half of the array
// containing even positioned elements
// in increasing order
sort(arr + (n + 1) / 2, arr + n);
// Printing all elements
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 7, 6, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
odd_even(arr, n);
return 0;
}
// This code is contributed by Pushpesh Raj
Producción
3 7 8 2 6
Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(1)