将最大值和最小值移动到拐角处的最小相邻交换-yiteyi-C++库

给定N个元素，求出所需交换的最小数量，使最大元素在开始处，最小元素在最后，条件是只允许交换相邻元素。 例如：

null

输入：a[]={3,1,5,3,5,5,2} 输出 : 6 步骤1：用1交换5，使数组成为{3,5,1,3,5,5,2} 步骤2：用3交换5，使数组成为{5,3,1,3,5,5,2} 第3步：将1与3交换，使数组成为{5,3,3,1,5,5,2} 第4步：在右边用5替换1，使数组成为{5,3,3,5,1,5,2} 第5步：在右边用5替换1，使数组成为{5,3,3,5,5,1,2} 第6步：将1与右边的2交换，使数组成为{5,3,3,5,5,2,1} 在执行6次交换操作后，5次在开头，1次在结尾输入：a[]={5,6,1,3} 输出 : 2

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法是找到最大元素的索引（设l）。如果最大元素在数组中多次出现，请查找最左边最大元素的索引。同样，找到最右边最小元素的索引（let r）。有两种情况可以解决这个问题。

案例1： 如果l
案例2： 如果l>r：交换次数=l+（n-r-2），因为在将较大的元件交换到前端时已经执行了一次交换

C++

                         // CPP program to count Minimum number                       
                         // of adjacent /swaps so that the largest element                       
                         // is at beginning and the smallest element                       
                         // is at last                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function that returns the minimum swaps                       
                         void                                     solve(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 int                                     maxx = -1, minn = a[0], l = 0, r = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // Index of leftmost largest element                       
                                                 if                                     (a[i] > maxx) {                       
                                                 maxx = a[i];                       
                                                 l = i;                       
                                                 }                       
           
                                                 // Index of rightmost smallest element                       
                                                 if                                     (a[i] <= minn) {                       
                                                 minn = a[i];                       
                                                 r = i;                       
                                                 }                       
                                                 }                       
                                                 if                                     (r < l)                       
                                                 cout << l + (n - r - 2);                       
                                                 else                       
                                                 cout << l + (n - r - 1);                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 5, 6, 1, 3 };                       
                                                 int                                     n =                                     sizeof                                     (a)/                                     sizeof                                     (a[0]);                       
                                                 solve(a, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count Minimum number                       
                         // of swaps so that the largest element                       
                         // is at beginning and the                       
                         // smallest element is at last                       
                         import                                     java.io.*;                       
                         class                                     GFG {                       
                                                 // Function performing calculations                       
                                                 public                                     static                                     void                                     minimumSwaps(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     maxx = -                                     1                                     , minn = a[                                     0                                     ], l =                                     0                                     , r =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
           
                                                 // Index of leftmost largest element                       
                                                 if                                     (a[i] > maxx) {                       
                                                 maxx = a[i];                       
                                                 l = i;                       
                                                 }                       
           
                                                 // Index of rightmost smallest element                       
                                                 if                                     (a[i] <= minn) {                       
                                                 minn = a[i];                       
                                                 r = i;                       
                                                 }                       
                                                 }                       
                                                 if                                     (r < l)                       
                                                 System.out.println(l + (n - r -                                     2                                     ));                       
                                                 else                       
                                                 System.out.println(l + (n - r -                                     1                                     ));                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String args[])                                     throws                                     IOException                       
                                                 {                       
                                                 int                                     a[] = {                                     5                                     ,                                     6                                     ,                                     1                                     ,                                     3                                     };                       
                                                 int                                     n = a.length;                       
                                                 minimumSwaps(a, n);                       
                                                 }                       
                         }                       

Python3

                         # Python3 program to count                       
                         # Minimum number of adjacent                       
                         # swaps so that the largest                       
                         # element is at beginning and                       
                         # the smallest element is at last.                       
                         def                                     minSwaps(arr):                       
                                                 '''Function that returns                       
                                                 the minimum swaps'''                       
                                   
                                                 n                                     =                                     len                                     (arr)                       
                                                 maxx, minn, l, r                                     =                                     -                                     1                                     , arr[                                     0                                     ],                                     0                                     ,                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 # Index of leftmost                       
                                                 # largest element                       
                                                 if                                     arr[i] > maxx:                       
                                                 maxx                                     =                                     arr[i]                       
                                                 l                                     =                                     i                       
                                   
                                                 # Index of rightmost                       
                                                 # smallest element                       
                                                 if                                     arr[i] <                                     =                                     minn:                       
                                                 minn                                     =                                     arr[i]                       
                                                 r                                     =                                     i                       
                                   
                                                 if                                     r < l:                       
                                                 print                                     (l                                     +                                     (n                                     -                                     r                                     -                                     2                                     ))                       
                                                 else                                     :                       
                                                 print                                     (l                                     +                                     (n                                     -                                     r                                     -                                     1                                     ))                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     5                                     ,                                     6                                     ,                                     1                                     ,                                     3                                     ]                       
           
                         minSwaps(arr)                       
           
                         # This code is contributed                       
                         # by Tuhin Patra                       

C#

                         // C# program to count Minimum                       
                         // number of swaps so that the                       
                         // largest element is at beginning                       
                         // and the smallest element is at last                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Function performing calculations                       
                                                 public                                     static                                     void                                     minimumSwaps(                                     int                                     []a,                       
                                                 int                                     n)                       
                                                 {                       
                                                 int                                     maxx = -1, l = 0,                       
                                                 minn = a[0], r = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
           
                                                 // Index of leftmost                       
                                                 // largest element                       
                                                 if                                     (a[i] > maxx)                       
                                                 {                       
                                                 maxx = a[i];                       
                                                 l = i;                       
                                                 }                       
           
                                                 // Index of rightmost                       
                                                 // smallest element                       
                                                 if                                     (a[i] <= minn)                       
                                                 {                       
                                                 minn = a[i];                       
                                                 r = i;                       
                                                 }                       
                                                 }                       
                                                 if                                     (r < l)                       
                                                 Console.WriteLine(l + (n - r - 2));                       
                                                 else                       
                                                 Console.WriteLine(l + (n - r - 1));                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
           
                                                 int                                     []a = { 5, 6, 1, 3 };                       
                                                 int                                     n = a.Length;                       
                                   
                                                 // Calling function                       
                                                 minimumSwaps(a, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to count Minimum                       
                         // number of adjacent /swaps so                       
                         // that the largest element is                       
                         // at beginning and the smallest                       
                         // element is at last                       
           
                         // Function that returns                       
                         // the minimum swaps                       
                         function                                     solve(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                                 $maxx                                     = -1;                                     $minn                                     =                                     $a                                     [0];                       
                                                 $l                                     = 0;                                     $r                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
           
                                                 // Index of leftmost                       
                                                 // largest element                       
                                                 if                                     (                                     $a                                     [                                     $i                                     ] >                                     $maxx                                     )                       
                                                 {                       
                                                 $maxx                                     =                                     $a                                     [                                     $i                                     ];                       
                                                 $l                                     =                                     $i                                     ;                       
                                                 }                       
           
                                                 // Index of rightmost                       
                                                 // smallest element                       
                                                 if                                     (                                     $a                                     [                                     $i                                     ] <=                                     $minn                                     )                       
                                                 {                       
                                                 $minn                                     =                                     $a                                     [                                     $i                                     ];                       
                                                 $r                                     =                                     $i                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 if                                     (                                     $r                                     <                                     $l                                     )                       
                                                 echo                                     $l                                     + (                                     $n                                     -                                     $r                                     - 2);                       
                                                 else                       
                                                 echo                                     $l                                     + (                                     $n                                     -                                     $r                                     - 1);                       
                         }                       
           
                         // Driver Code                       
                         $a                                     =                                     array                                     (5, 6, 1, 3);                       
                         $n                                     =                                     count                                     (                                     $a                                     );                       
                         solve(                                     $a                                     ,                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to count Minimum number                       
                         // of adjacent /swaps so that the largest element                       
                         // is at beginning and the smallest element                       
                         // is at last                       
           
                         // Function that returns the minimum swaps                       
                         function                                     solve(a, n)                       
                         {                       
                                                 let maxx = -1, minn = a[0], l = 0, r = 0;                       
                                                 for                                     (let i = 0; i < n; i++) {                       
                                                 // Index of leftmost largest element                       
                                                 if                                     (a[i] > maxx) {                       
                                                 maxx = a[i];                       
                                                 l = i;                       
                                                 }                       
                                                 // Index of rightmost smallest element                       
                                                 if                                     (a[i] <= minn) {                       
                                                 minn = a[i];                       
                                                 r = i;                       
                                                 }                       
                                                 }                       
                                                 if                                     (r < l)                       
                                                 document.write(l + (n - r - 2));                       
                                                 else                       
                                                 document.write( l + (n - r - 1));                       
                         }                       
           
                         // Driver Code                       
                         let a = [ 5, 6, 1, 3 ];                       
                         let n = a.length;                       
                         solve(a, n);                       
           
                         </script>                       

输出：

时间复杂性： O（N）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章