最小化交换以重新排列数组,以使索引和相应元素的奇偶校验相同

2021年5月1日17:58:48 发表评论 99 次浏览

本文概述

给定数组A[],找到修改给定数组A[]所需的最小交换操作,使数组中的每个索引的奇偶校验(i) =奇偶校验(A[i]),其中奇偶校验(x) = x % 2。如果不可能获得这样的安排,那么输出-1。

例子:

输入:A [] = {2, 4, 3, 1, 5, 6}
输出:2
说明:
交换(4, 3)和(5, 6)会将数组修改为[2, 3, 4, 1, 6 , 5], 这样i和A [i]的奇偶校验对于所有索引都是相同的。
输入:A [] = {1, 2, 5, 7}
输出:-1
说明:无法根据所需条件重新排列给定的数组。

方法:

解决上述问题的最优方法是选择parity(i)和parity(A[i])不相同的索引。

  • 初始化两个变量需要和需要甚至to0它将存储每个元素的奇偶校验。检查索引的奇数是否为奇数, 然后增加需要值加1, 否则增加需要甚至.
  • If需要和需要甚至不一样, 则无法进行所需的安排。
  • 否则, 最终结果将通过需要变量, 因为它是所需的操作数。这是因为在任何时候, 我们都选择一个奇偶校验元素, 其奇偶校验与它们的索引奇偶校验不相同, 并且类似地选择一个偶数元素并交换它们。

下面是上述方法的实现:

C ++

//C++ implementation to minimize
//swaps required to rearrange
//array such that parity of index and
//corresponding element is same
#include <bits/stdc++.h>
using namespace std;
 
//Function to return the
//parity of number
int parity( int x)
{
     return x % 2;
     
}
 
//Function to return minimum
//number of operations required
int solve( int a[], int size)
{
     
     //Initialize needodd and
     //needeven value by 0
     int needeven = 0;
     int needodd = 0;
     
     for ( int i = 0; i <size; i++)
     {
         if (parity(i) != parity(a[i]))
         {
             
             //Check if parity(i) is odd
             if (parity(i) % 2)
             {
                 
                 //increase needodd
                 //as we need odd no
                 //at that position.
                 needodd++;
             }
             else
             {
 
                 //increase needeven
                 //as we need even
                 //number at that position
                 needeven++;
             }
         }
     }
     
     //If needeven and needodd are unequal
     if (needeven != needodd)
         return -1;
     else
         return needodd;
}
 
//Driver Code
int main()
{
     int a[] = { 2, 4, 3, 1, 5, 6};
     int n = sizeof (a) /sizeof (a[0]);
 
     //Function call
     cout <<solve(a, n) <<endl;
 
     return 0;
}
 
//This code is contributed by venky07

Java

//Java implementation to minimize 
//swaps required to rearrange 
//array such that parity of index and 
//corresponding element is same
import java.util.*;
 
class GFG{
     
//Function to return the
//parity of number
static int parity( int x)
{
     return x % 2 ;
}
 
//Function to return minimum
//number of operations required
static int solve( int a[], int size)
{
     
     //Initialize needodd and
     //needeven value by 0
     int needeven = 0 ;
     int needodd = 0 ;
     
     for ( int i = 0 ; i <size; i++)
     {
         if (parity(i) != parity(a[i]))
         {
             
             //Check if parity(i) is odd
             if (parity(i) % 2 == 1 )
             {
                 
                 //Increase needodd
                 //as we need odd no
                 //at that position.
                 needodd++;
             }
             else
             {
                 
                 //Increase needeven
                 //as we need even
                 //number at that position
                 needeven++;
             }
         }
     }
     
     //If needeven and needodd are unequal
     if (needeven != needodd)
         return - 1 ;
     else
         return needodd;
}
 
//Driver Code
public static void main (String[] args)
{
     int a[] = { 2 , 4 , 3 , 1 , 5 , 6 };
     int n = a.length;
     
     //Function call
     System.out.println(solve(a, n));
}
}
 
//This code is contributed by offbeat

Python3

# Python3 implementation to minimize
# swaps required to rearrange
# array such that parity of index and
# corresponding element is same
 
# Function to return the
# parity of number
def parity(x):
     return x % 2
 
# Function to return minimum
# number of operations required
 
def solve(a, size):
     
     # Initialize needodd and
     # needeven value by 0
     needeven = 0
     needodd = 0
     for i in range (size):
                 
         if parity(i)! = parity(a[i]):
             
             # Check if parity(i) is odd
             if parity(i) % 2 :
                 
                 # increase needodd
                 # as we need odd no
                 # at that position.
                 needodd + = 1
             else :
                 # increase needeven
                 # as we need even
                 # number at that position
                 needeven + = 1
     
     # If needeven and needodd are unequal
     if needodd ! = needeven:
         return - 1
         
     return needodd
     
# Driver code    
if __name__ = = "__main__" :
     
     a = [ 2 , 4 , 3 , 1 , 5 , 6 ]
     n = len (a)
     print (solve(a, n))

C#

//C# implementation to minimize 
//swaps required to rearrange 
//array such that parity of index and 
//corresponding element is same
using System;
class GFG{
     
//Function to return the
//parity of number
static int parity( int x)
{
   return x % 2;
}
 
//Function to return minimum
//number of operations required
static int solve( int [] a, int size)
{    
   //Initialize needodd and
   //needeven value by 0
   int needeven = 0;
   int needodd = 0;
 
   for ( int i = 0; i <size; i++)
   {
     if (parity(i) != parity(a[i]))
     {
       //Check if parity(i) is odd
       if (parity(i) % 2 == 1)
       {
         //Increase needodd
         //as we need odd no
         //at that position.
         needodd++;
       }
       else
       {
         //Increase needeven
         //as we need even
         //number at that position
         needeven++;
       }
     }
   }
 
   //If needeven and needodd are unequal
   if (needeven != needodd)
     return -1;
   else
     return needodd;
}
 
//Driver Code
public static void Main ()
{
   int [] a = {2, 4, 3, 1, 5, 6};
   int n = a.Length;
 
   //Function call
   Console.Write(solve(a, n));
}
}
 
//This code is contributed by Chitranayal

输出如下:

2

一盏木

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: