极客笔记Java 将数组中的0放置在左侧，1放置在右侧
分离是软件工程领域的一个过程，它强制代码依赖于那些不使用的方法。分离接口被称为ISP，它将庞大的接口分割成小的接口。在Java环境中，实现分离原则有很多优势。它增加了特定代码的可读性，以及帮助以方便的方式维护特定代码。
示例：数组中以随机方式存在着7和16。我们需要将7放置在左侧，16放置在右侧。这里的基本目标是遍历这些元素。
Input array = [7,16,7,16,7,16,7,16]
Output array = [7,7,7,7,16,16,16,16]
让我们讨论将分离过程应用于数组以将0放在左边，1放在右边的实现。
分离数组中0放在左边，1放在右边的算法
- 步骤1-开始。
-
步骤2-建立两个不同的索引。
-
步骤3-将第一个索引声明为0（左）。
-
步骤4-将第二个索引声明为n-1（右）。
-
步骤5-遵循条件：left
-
步骤6-增加整个索引left（在其上的0）。
-
步骤7-减少整个索引right（在其上的1）。
-
步骤8-如果left
- 步骤9-否则，继续该过程。
语法
int left = 0, right = size-1;
while (left < right){
while (array[left] == 0 && left < right)
left++;
while (array[right] == 1 && left < right)
right--;
if (left < right){
array[left] = 0;
array[right] = 1;
left++;
right--;
}
}
在这个语法中，我们可以看到函数如何将数组中所有的0都分割到左边，将1都分割到右边。
- 取两个指针;
- 从开头（索引=0）开始遍历元素X
-
从末尾（索引=array.length-1）开始遍历类型1的元素
-
初始化type0 = 0
-
初始化type1 = array.length-1
-
将1放到数组的右边是必要的。在完成此过程之后，0肯定会位于左边。
方法
-
方法1-通过计数使用分离方法
-
方法2-通过对数组使用排序方法
-
方法3-通过使用指针
-
方法4-通过使用蛮力方法
方法1：通过计数使用分离方法
过程：这里是通过计数使用分离方法的逐步过程。
- 计算0的个数。
-
遍历整个数组。
-
搜索元素。
-
维护数据并逐步增加，直到结果出现。
-
打印。
-
剩余的1的个数。
-
打印剩余的个数。
这个特定代码的时间复杂度：O(n)，辅助空间：O(1)。
示例1
import java.util.*;
import java.util.Arrays;
public class tutorialspoint {
static void segregate7and16(int arr[], int n){
int count = 0;
for (int a = 0; a < n; a++) {
if (arr[a] == 0)
count++;
}
for (int a = 0; a < count; a++)
arr[a] = 0;
for (int i = count; i < n; i++)
arr[i] = 1;
}
static void print(int arr[], int n){
System.out.print("Array after segregation list is here ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args){
int arr[] = new int[] { 7, 16, 7, 16, 16, 16,7,16 };
int n = arr.length;
segregate7and16(arr, n);
print(arr, n);
}
}
输出
Array after segregation list is here 1 1 1 1 1 1 1 1
方法2：通过对数组使用排序方法
sort()是Java Until类的一个方法。
- 语法是 –
public static void sort(int[] arr, int from_Index, int to_Index)
- 参数:
- arr- 要排序的数组
-
from_Index – 要排序的起始位置（包括）。
-
to_Index – 要排序的结束位置（不包括）。
示例2
import java.util.*;
public class tutoriaspoint {
static void print(int arr[], int n){
System.out.print("Array after segregation is ");
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
}
public static void main(String[] args){
int arr[] = new int[] { 0, 1, 0, 1, 1, 1 };
int n = arr.length;
Arrays.sort(arr);
print(arr, n);
}
}
输出
Array after segregation is 0 0 1 1 1 1
方法3：通过使用指针
需要维护左指针并将其与左侧位置交换。当在数组中找到零并增加左指针。
示例3
import java.util.*;
import java.io.*;
public class tutorialspoint {
static void print(int a[]){
System.out.print("Array after segregation is: ");
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
}
public static void main(String[] args){
int a[] = { 1, 1, 0, 0, 0, 0, 1, 1 };
int left = 0;
for (int i = 0; i < a.length; ++i) {
if (a[i] == 0) {
int temp = a[left];
a[left] = a[i];
a[i] = temp;
++left;
}
}
print(a);
}
}
输出
Array after segregation is: 0 0 0 0 1 1 1 1
方法4：通过使用Brute Force方法
维护左指针并将其与左侧的位置交换。当数组中找到0并增加左指针。
该方法将首先计算数字的数量，然后根据0和1填充数据。
流程：
- 该流程将根据数组大小计算数字的数量。
-
在计数后将开始填充。
示例4
public class segregatearray {
static void segregating0sand1s(int arr[], int n){
int count = 0; //count no of zeros in array
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
count++;
}
for (int i = 0; i < count; i++)
arr[i] = 0; // fill the array with 0 until termination
for (int i = count; i < n; i++)
arr[i] = 1; // fill remaining array with 1 until termination
}
static void print(int arr[], int n){
System.out.print("Array after the process 0s and 1s are ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args){
int arr[] = new int[]{ 1, 1, 0, 0, 1, 1 };
int n = arr.length;
segregating0sand1s(arr, n);
print(arr, n);
}
}
输出
Array after the process 0s and 1s are 0 0 1 1 1 1
结论
在本文中，我们学习了如何将所有的0分离到左边，将所有的1分离到右边，并讨论了不同的方法、伪代码、实现和代码。在这里，我们定义了一个数组，并将该数组以及其总长度传递给函数。