Java 程序将数组左侧的 0 与右侧的 1 隔离
隔离是软件工程领域的一个过程,其中代码强制依赖于未使用的方法。隔离接口称为 ISP。它分割本质上庞大的接口。在 Java 环境中,实现隔离原则有很多优势。它增加了特定代码的可读性。以及有助于以方便的方式维护该特定代码。
示例:有一个随机包含 7 和 16 的数组。我们必须将 7 隔离在左侧,将 16 隔离在右侧。基本目标是遍历这些元素
输入数组 = [7,16,7,16,7,16,7,16] 输出数组 = [7,7,7,7,16,16,16,16]
让我们讨论一下对数组执行左侧 0 和右侧 1 的分离过程的实现。
分离数组左侧 0 和右侧 1 的算法:-
步骤 1 - 开始。
步骤 2 - 建立两个不同的索引。
步骤 3 - 将第一个声明为 0。(左)
步骤 4 -将第二个声明为 n-1。(右)
步骤 5 − 遵循条件:左<右。
步骤 6 − 将整个索引向左增加(0 为该位置)
步骤 7 − 将整个索引向右减少(1 为该位置)
步骤 8 − 如果左<右,则交换位置。
步骤 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。
获取两个指针;
对于元素 X,从开头 (index = 0) 开始
type1(对于元素 1)从结尾 (index = array.length-1) 开始。
初始化 type0 = 0
type1 = array.length-1
必须将 1 放在数组的右侧。完成此过程后,0 肯定会向左移动。
方法
方法 1 - 使用计数分离方法
方法 2 - 使用数组上的排序方法
方法 3 - 使用指针
方法 4 - 使用蛮力方法
使用计数分离方法
过程:以下是计数分离方法的分步过程。
计算 0 的数量。
遍历整个数组。
搜索元素。
维护数据并递增,直到出现结果。
打印。
剩余的 1 的数量。
打印剩余的 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);
}
}
输出
分类后的数组列表如下 1 1 1 1 1 1 1 1
对数组使用排序方法
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);
}
}
输出
分割后的数组为 0 0 1 1 1 1
使用指针
需要保留左指针,并将其与左指针的位置交换。当在数组中找到零时,增加左指针。
示例 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);
}
}
输出
分离后的数组为:0 0 0 0 1 1 1 1
使用蛮力法
保留左指针并将其与左指针的位置交换。当在数组中找到零时,增加左指针。
该方法将首先计数。然后用0和1相应地填充数据。
过程:
该过程将根据数组大小计数。
计数后开始填充。
示例4
public class segregatearray {
static void segregating0sand1s(int arr[], int n){
int count = 0; //计算数组中零的数量
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
count++;
}
for (int i = 0; i < count; i++)
arr[i] = 0; // 用 0 填充数组直到终止
for (int i = count; i < n; i++)
arr[i] = 1; // 用 1 填充剩余数组直到终止
}
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 分离在右侧,即分离 0 和 1,以及其不同的方法、伪代码、实现和代码。在这里,我们定义了一个数组,并将该数组及其总长度传递给函数。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

