数组在给定范围内的三向分区-yiteyi-C++库

给定一个数组和一个范围[ 洛瓦尔 , 海瓦尔 ]，将数组按范围进行分区，使数组分为三部分。 1）所有元素都小于 洛瓦尔 先来。 2）范围内的所有元素 洛瓦尔 到 海夫瓦尔 下一个来。 3）所有元素大于 海夫瓦尔 最后出现。三个集合中的单个元素可以以任何顺序出现。

null

例如：

Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}          lowVal = 14, highVal = 20Output: arr[] = {1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54}Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}         lowVal = 20, highVal = 20       Output: arr[] = {1, 14, 5, 4, 2, 1, 3, 20, 20, 98, 87, 32, 54}

图片[1]-数组在给定范围内的三向分区-yiteyi-C++库

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 就是对数组进行排序。这个解决方案需要很多额外的重新排列，并且需要O（n logn）时间。一 有效解决方案 基于基于荷兰国旗的快速排序 .我们从左边遍历给定的数组元素。我们跟踪两个指针，第一个（在下面的代码中称为start）从开始存储较小元素（小于范围）的下一个位置；第二个（在下面的代码中称为end）存储从末端开始的更大元素的下一个位置。

C++

                         // C++ program to implement three way partitioning                       
                         // around a given range.                       
                         #include<iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Partitions arr[0..n-1] around [lowVal..highVal]                       
                         void                                     threeWayPartition(                                     int                                     arr[],                                     int                                     n,                       
                                                 int                                     lowVal,                                     int                                     highVal)                       
                         {                       
                                                 // Initialize ext available positions for                       
                                                 // smaller (than range) and greater elements                       
                                                 int                                     start = 0, end = n-1;                       
           
                                                 // Traverse elements from left                       
                                                 for                                     (                                     int                                     i=0; i<=end;)                       
                                                 {                       
                                                 // If current element is smaller than                       
                                                 // range, put it on next available smaller                       
                                                 // position.                       
                                                 if                                     (arr[i] < lowVal)                       
                                                 {                       
                                                 //if i and start are same in that case we can't swap                       
                                                 //swap only if i is greater than start                       
                                                 if                                     (i==start)                       
                                                 {                       
                                                 start++;                       
                                                 i++;                       
                                                 }                       
                                                 else                       
                                                 swap(arr[i++], arr[start++]);                       
                                                 }                       
           
                                                 // If current element is greater than                       
                                                 // range, put it on next available greater                       
                                                 // position.                       
                                                 else                                     if                                     (arr[i] > highVal)                       
                                                 swap(arr[i], arr[end--]);                       
           
                                                 else                       
                                                 i++;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87,                       
                                                 98, 3, 1, 32};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
           
                                                 threeWayPartition(arr, n, 10, 20);                       
           
                                                 cout <<                                     "Modified array "                                     ;                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                         }                       

JAVA

                         // Java program to implement three way partitioning                       
                         // around a given range.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // Partitions arr[0..n-1] around [lowVal..highVal]                       
                                                 public                                     static                                     void                                     threeWayPartition(                                     int                                     [] arr,                                     int                                     lowVal,                                     int                                     highVal)                       
                                                 {                       
                                   
                                                 int                                     n = arr.length;                       
                                   
                                                 // Initialize ext available positions for                       
                                                 // smaller (than range) and greater elements                       
                                                 int                                     start =                                     0                                     , end = n-                                     1                                     ;                       
                                   
                                                 // Traverse elements from left                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <= end;)                       
                                                 {                       
                                   
                                                 // If current element is smaller than                       
                                                 // range, put it on next available smaller                       
                                                 // position.                       
                                   
                                                 if                                     (arr[i] < lowVal)                       
                                                 {                       
                                   
                                                 int                                     temp = arr[start];                       
                                                 arr[start] = arr[i];                       
                                                 arr[i] = temp;                       
                                                 start++;                       
                                                 i++;                       
                                   
                                                 }                       
                                   
                                                 // If current element is greater than                       
                                                 // range, put it on next available greater                       
                                                 // position.                       
                                                 else                                     if                                     (arr[i] > highVal)                       
                                                 {                       
                                   
                                                 int                                     temp = arr[end];                       
                                                 arr[end] = arr[i];                       
                                                 arr[i] = temp;                       
                                                 end--;                       
                                   
                                                 }                       
                                   
                                                 else                       
                                                 i++;                       
                                                 }                       
                                   
                                                 }                       
                                   
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                   
                                   
                                                 int                                     arr[] = {                                     1                                     ,                                     14                                     ,                                     5                                     ,                                     20                                     ,                                     4                                     ,                                     2                                     ,                                     54                                     ,                                     20                                     ,                                     87                                     ,                                     98                                     ,                                     3                                     ,                                     1                                     ,                                     32                                     };                       
                                   
                                                 threeWayPartition(arr,                                     10                                     ,                                     20                                     );                       
                                   
                                                 System.out.println(                                     "Modified array "                                     );                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i < arr.length; i++)                       
                                                 {                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                                   
                                                 }                       
                                                 }                       
                         }                       
           
                         //This code is contributed by Dheerendra Singh                       

Python3

                         # Python3 program to implement three way                       
                         # partitioning around a given range.                       
           
                         # Partitions arr[0..n-1] around [lowVal..highVal]                       
                         def                                     threeWayPartition(arr, n, lowVal, highVal):                       
           
                                                 # Initialize ext available positions for                       
                                                 # smaller (than range) and greater elements                       
                                                 start                                     =                                     0                       
                                                 end                                     =                                     n                                     -                                     1                       
                                                 i                                     =                                     0                       
           
                                                 # Traverse elements from left                       
                                                 while                                     i <                                     =                                     end:                       
           
                                                 # If current element is smaller than                       
                                                 # range, put it on next available smaller                       
                                                 # position.                       
                                                 if                                     arr[i] < lowVal:                       
                                                 arr[i], arr[start]                                     =                                     arr[start], arr[i]                       
                                                 i                                     +                                     =                                     1                       
                                                 start                                     +                                     =                                     1                       
           
                                                 # If current element is greater than                       
                                                 # range, put it on next available greater                       
                                                 # position.                       
                                                 elif                                     arr[i] > highVal:                       
                                                 arr[i], arr[end]                                     =                                     arr[end], arr[i]                       
                                                 end                                     -                                     =                                     1                       
           
                                                 else                                     :                       
                                                 i                                     +                                     =                                     1                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 arr                                     =                                     [                                     1                                     ,                                     14                                     ,                                     5                                     ,                                     20                                     ,                                     4                                     ,                                     2                                     ,                                     54                                     ,                       
                                                 20                                     ,                                     87                                     ,                                     98                                     ,                                     3                                     ,                                     1                                     ,                                     32                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
           
                                                 threeWayPartition(arr, n,                                     10                                     ,                                     20                                     )                       
           
                                                 print                                     (                                     "Modified array"                                     )                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 print                                     (arr[i], end                                     =                                     " "                                     )                       
           
                         # This code is contributed by                       
                         # sanjeev2552                       

C#

                         // C# program to implement three way                       
                         // partitioning around a given range.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Partitions arr[0..n-1]                       
                                                 // around [lowVal..highVal]                       
                                                 public                                     static                                     void                                     threeWayPartition(                                     int                                     [] arr,                       
                                                 int                                     lowVal,                                     int                                     highVal)                       
                                                 {                       
                                                 int                                     n = arr.Length;                       
           
                                                 // Initialize ext available positions for                       
                                                 // smaller (than range) and greater elements                       
                                                 int                                     start = 0, end = n - 1;                       
           
                                                 // Traverse elements from left                       
                                                 for                                     (                                     int                                     i = 0; i <= end;) {                       
           
                                                 // If current element is smaller than                       
                                                 // range, put it on next available smaller                       
                                                 // position.                       
           
                                                 if                                     (arr[i] < lowVal) {                       
           
                                                 int                                     temp = arr[start];                       
                                                 arr[start] = arr[i];                       
                                                 arr[i] = temp;                       
                                                 start++;                       
                                                 i++;                       
                                                 }                       
           
                                                 // If current element is greater than                       
                                                 // range, put it on next available greater                       
                                                 // position.                       
                                                 else                                     if                                     (arr[i] > highVal) {                       
           
                                                 int                                     temp = arr[end];                       
                                                 arr[end] = arr[i];                       
                                                 arr[i] = temp;                       
                                                 end--;                       
                                                 }                       
           
                                                 else                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 1, 14, 5, 20, 4, 2, 54,                       
                                                 20, 87, 98, 3, 1, 32 };                       
           
                                                 threeWayPartition(arr, 10, 20);                       
           
                                                 Console.WriteLine(                                     "Modified array "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++) {                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // This article is contributed by vt_m.                       

Javascript

                         <script>                       
           
                         // JavaScript program to implement three                       
                         // way partitioning around a given range.                       
           
                         // Partitions arr[0..n-1] around [lowVal..highVal]                       
                         function                                     threeWayPartition(arr, n, lowVal, highVal)                       
                         {                       
                                   
                                                 // Initialize ext available positions for                       
                                                 // smaller (than range) and greater elements                       
                                                 let start = 0, end = n - 1;                       
           
                                                 // Traverse elements from left                       
                                                 for                                     (let i = 0; i <= end;)                       
                                                 {                       
                                   
                                                 // If current element is smaller than                       
                                                 // range, put it on next available smaller                       
                                                 // position.                       
                                                 if                                     (arr[i] < lowVal)                       
                                                 {                       
                                                 let temp = arr[start];                       
                                                 arr[start] = arr[i];                       
                                                 arr[i] = temp;                       
                                                 start++;                       
                                                 i++;                       
                                                 }                       
           
                                                 // If current element is greater than                       
                                                 // range, put it on next available greater                       
                                                 // position.                       
                                                 else                                     if                                     (arr[i] > highVal)                       
                                                 {                       
                                                 let temp = arr[end];                       
                                                 arr[end] = arr[i];                       
                                                 arr[i] = temp;                       
                                                 end--;                       
                                                 }                       
                                                 else                       
                                                 i++;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         let arr = [ 1, 14, 5, 20, 4, 2, 54,                       
                                                 20, 87, 98, 3, 1, 32 ];                       
                         let n = arr.length;                       
           
                         threeWayPartition(arr, n, 10, 20);                       
           
                         document.write(                                     "Modified array <br>"                                     );                       
                         for                                     (let i = 0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
           
                         // This code is contributed by Surbhi Tyagi.                       
           
                         </script>                       

输出：

Modified array 1 5 4 2 1 3 14 20 20 98 87 32 54

时间复杂性： O（n） 辅助空间： O（1）

请进来雅虎本文由 罗什尼·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章