Dada una array desordenada de elementos distintos. La tarea es contar el número de líneas cruzadas formadas en los elementos de una array después de ordenar los elementos de la array.
Nota: dibuje una línea entre los mismos elementos de la array antes de ordenar y después de ordenar los elementos de la array.
Ejemplos:
Input : arr[] = { 3, 2, 1, 4, 5 }
Output : 3
before sort: 3 2 1 4 5
\ | / | |
\|/ | |
/ | \ | |
After sort : 1 2 3 4 5
line (1 to 1) cross line (2 to 2)
line (1 to 1) cross line (3 to 3)
line (2 to 2) cross line (3 to 3)
Note: the line between two 4s and the line
between two 5s don't cross any other lines;
Input : arr[] = { 5, 4, 3, 1 }
Output : 6
La solución simple de este problema se basa en el ordenamiento por inserción . simplemente elegimos cada elemento de la array uno por uno e intentamos encontrar su posición adecuada en la array ordenada. Durante la búsqueda de la posición adecuada de un elemento, tenemos que cruzar toda la línea_elemento cuyo valor es mayor que el elemento actual.
A continuación se muestra la implementación de la idea anterior:
C++
// c++ program to count cross line in array
#include <bits/stdc++.h>
using namespace std;
// function return count of cross line in an array
int countCrossLine(int arr[], int n)
{
int count_crossline = 0;
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
// increment cross line by one
count_crossline++;
}
arr[j + 1] = key;
}
return count_crossline;
}
// driver program to test above function
int main()
{
int arr[] = { 4, 3, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countCrossLine(arr, n) << endl;
return 0;
}
Java
// Java program to count
// cross line in array
class GFG
{
static int countCrossLine(int arr[],
int n)
{
int count_crossline = 0;
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
// Move elements of arr[0..i-1],
// that are greater than key,
// to one position ahead of
// their current position
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
// increment cross
// line by one
count_crossline++;
}
arr[j + 1] = key;
}
return count_crossline;
}
// Driver Code
public static void main(String args[])
{
int arr[] = new int[]{ 4, 3, 1, 2 };
int n = arr.length;
System.out.print(countCrossLine(arr, n));
}
}
// This code is contributed by Sam007
Python3
# Python3 program to count # cross line in array def countCrossLine(arr, n): count_crossline = 0; i, key, j = 0, 0, 0; for i in range(1, n): key = arr[i]; j = i - 1; # Move elements of arr[0..i-1], # that are greater than key, # to one position ahead of # their current position while (j >= 0 and arr[j] > key): arr[j + 1] = arr[j]; j = j - 1; # increment cross # line by one count_crossline += 1; arr[j + 1] = key; return count_crossline; # Driver Code if __name__ == '__main__': arr = [4, 3, 1, 2]; n = len(arr); print(countCrossLine(arr, n)); # This code is contributed by PrinciRaj1992
C#
// C# program to count cross line in array
using System;
class GFG {
// function return count of cross line
// in an array
static int countCrossLine(int []arr, int n)
{
int count_crossline = 0;
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1],
that are greater than key, to one
position ahead of their current
position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
// increment cross line by one
count_crossline++;
}
arr[j + 1] = key;
}
return count_crossline;
}
// Driver code
public static void Main()
{
int []arr = new int[]{ 4, 3, 1, 2 };
int n = arr.Length;
Console.Write(countCrossLine(arr, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to count
// cross line in array
// Function return count
// of cross line in an array
function countCrossLine($arr, $n)
{
$count_crossline = 0;
$i; $key; $j;
for ($i = 1; $i < $n; $i++)
{
$key = $arr[$i];
$j = $i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while ($j >= 0 and $arr[$j] > $key)
{
$arr[$j + 1] = $arr[$j];
$j = $j - 1;
// increment cross line by one
$count_crossline++;
}
$arr[$j + 1] = $key;
}
return $count_crossline;
}
// Driver Code
$arr = array( 4, 3, 1, 2 );
$n = count($arr);
echo countCrossLine($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to count cross line in array
// function return count of cross line in an array
function countCrossLine( arr, n)
{
let count_crossline = 0;
let i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
// increment cross line by one
count_crossline++;
}
arr[j + 1] = key;
}
return count_crossline;
}
// driver code
let arr = [ 4, 3, 1, 2 ];
let n = arr.length;
document.write(countCrossLine(arr, n) + "</br");
</script>
Producción:
5
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)
Solución eficiente basada en el ordenamiento por fusión y el conteo de inversiones .
lets we have arr[] { 2, 4, 1, 3 }
\ \ / /
\ / \ /
/ \ / \
After sort arr[] { 1, 2, 3, 4 }
and here all inversion are (2, 1), (4, 1), (4, 3)
that mean line 1 : cross line 4, 2
line 2 : cross line 1
line 4 : cross line 3, 1
line 3 : cross line 3
so total unique cross_line are: 3
Durante mer
A continuación se muestra la implementación de la idea anterior.
C++
// c++ program to count cross line in array
#include <bits/stdc++.h>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r, int* count_crossline)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
//====================================//
//======= MAIN PORTION OF CODE ======//
//===================================//
// add all line which is cross by current element
*count_crossline += (n1 - i);
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r, int* count_crossline)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m, count_crossline);
mergeSort(arr, m + 1, r, count_crossline);
merge(arr, l, m, r, count_crossline);
}
}
// function return count of cross line in an array
int countCrossLine(int arr[], int n)
{
int count_crossline = 0;
mergeSort(arr, 0, n - 1, &count_crossline);
return count_crossline;
}
// driver program to test above function
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countCrossLine(arr, n) << endl;
return 0;
}
Java
// Java program to count cross line in array
import java.util.*;
class GFG
{
static int count_crossline;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
{
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++)
{
R[j] = arr[m + 1 + j];
}
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
//====================================//
//======= MAIN PORTION OF CODE ======//
//===================================//
// add all line which is cross by current element
count_crossline += (n1 - i);
j++;
}
k++;
}
/* Copy the remaining elements of L[],
if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[],
if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
static void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// function return count of cross line in an array
static int countCrossLine(int arr[], int n)
{
mergeSort(arr, 0, n - 1);
return count_crossline;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
System.out.println(countCrossLine(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python program to count cross line in array count_crossline=0 # Merges two subarrays of arr[]. # First subarray is arr[l..m] # Second subarray is arr[m+1..r] def merge(arr,l,m,r): global count_crossline n1=m-l+1 n2=r-m # create temp arrays L=[0]*n1 R=[0]*n2 # Copy data to temp arrays L[] and R[] for i in range(n1): L[i]=arr[l+i] for j in range(n2): R[j]=arr[m+1+j] # Merge the temp arrays back into arr[l..r] i=0 # Initial index of first subarray j=0 # Initial index of second subarray k=l # Initial index of merged subarray while(i<n1 and j<n2): if(L[i]<=R[j]): arr[k]=L[i] i+=1 else: arr[k]=R[j] # ==================================== # ======= MAIN PORTION OF CODE ====== # =================================== # add all line which is cross by current element count_crossline+=(n1-i) j+=1 k+=1 # Copy the remaining elements of L[], if there # are any while(i<n1): arr[k]=L[i] i+=1 k+=1 # Copy the remaining elements of R[], if there # are any while(j<n2): arr[k]=R[j] j+=1 k+=1 # l is for left index and r is right index of the # sub-array of arr to be sorted def mergeSort(arr,l,r): if(l<r): # Same as (l+r)/2, but avoids overflow for # large l and h m=l+(r-l)//2 # Sort first and second halves mergeSort(arr,l,m) mergeSort(arr,m+1,r) merge(arr,l,m,r) # function return count of cross line in an array def countCrossLine(arr,n): mergeSort(arr,0,n-1) return count_crossline # driver program to test above function arr=[ 12, 11, 13, 5, 6, 7 ] n=len(arr) print(countCrossLine(arr,n)) # This code is contributed by Pushpesh Raj.
C#
// C# program to count cross line in array
using System;
class GFG
{
static int count_crossline;
// Merges two subarrays of []arr.
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
static void merge(int []arr, int l,
int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
{
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++)
{
R[j] = arr[m + 1 + j];
}
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
//====================================//
//======= MAIN PORTION OF CODE ======//
//===================================//
// add all line which is cross by current element
count_crossline += (n1 - i);
j++;
}
k++;
}
/* Copy the remaining elements of L[],
if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[],
if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
static void mergeSort(int []arr, int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// function return count of cross line in an array
static int countCrossLine(int []arr, int n)
{
mergeSort(arr, 0, n - 1);
return count_crossline;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {12, 11, 13, 5, 6, 7};
int n = arr.Length;
Console.WriteLine(countCrossLine(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to count cross line in array
let count_crossline = 0;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr, l, m, r)
{
let i, j, k;
let n1 = m - l + 1;
let n2 = r - m;
/* create temp arrays */
let L = [];
let R = [];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
{
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++)
{
R[j] = arr[m + 1 + j];
}
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
//====================================//
//======= MAIN PORTION OF CODE ======//
//===================================//
// add all line which is cross by current element
count_crossline += (n1 - i);
j++;
}
k++;
}
/* Copy the remaining elements of L[],
if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[],
if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
function mergeSort(arr, l, r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
let m = l + Math.floor((r - l) / 2);
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// function return count of cross line in an array
function countCrossLine(arr, n)
{
mergeSort(arr, 0, n - 1);
document.write(count_crossline);
}
// Driver code
let arr = [12, 11, 13, 5, 6, 7];
let n = arr.length;
countCrossLine(arr, n);
// This code is contributed by code_hunt.
</script>
Producción:
10
Complejidad de tiempo: O(nlogn)
Referencia: https://www.careercup.com/question?id=5669565693427712
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA