配列を並べ替える方法
int[] A = {0,1,1,0,1,0,1,1,0}
質問する
10226 次
17 に答える
10
配列を1回だけトラバースすることで、実際にこの配列を並べ替えることができます。
これが私のコードの抜粋です：
int arr[] = {1,1,1,1,0, 0,1,0,1,1,1};
int arrb[] = new int[arr.length];
int zeroInsertIndex = 0;
int oneInsertIndex =arrb.length-1;
for(int i=0; i<arr.length; i++){
if(arr[i] == 1)
arrb[oneInsertIndex--] = 1;
else if (arr[i] == 0)
arrb[zeroInsertIndex++] = 0;
}
for(int i=0;i<arrb.length;i++)
System.out.print(arrb[i] + " ");
于 2016-08-04T10:33:23.220 に答える
4
Arrays.sortは明白で単純なO（n log n）ソリューションですが、この特殊なケースにはO（n）ソリューションがあります。
- ゼロの数、zeroCountをカウントします。
- 最初のzeroCount要素を0で埋め、残りの要素を1で埋めます。
これには、アレイ上で2回のパスが必要です。
より一般的には、個別の値の数が少ない配列は、各値が表示される回数をカウントし、それに応じて配列に入力することで並べ替えることができます。
于 2013-02-07T07:06:34.593 に答える
2
配列には0と1しか含まれていないため、配列内のすべての要素を合計してから、最後にそれらの多くの「1」を付けて配列をリセットし、最初に「0」を残します。時間計算量も一定の空間でO（n）です。だから、それは最高で簡単なもののようです。
public static void main(String[] args) {
int[] A = { 0, 1, 1, 0, 1, 0, 1, 1, 0 };
int sum = 0;
for (int i = 0; i < A.length; i++)
sum = sum + A[i];
Arrays.fill(A, A.length - sum, A.length, 1);
Arrays.fill(A, 0, A.length - sum, 0);
System.out.println(Arrays.toString(A));
}
これを試してみてください私は上記のアルゴリズムを実装しました。
出力：
[0, 0, 0, 0, 1, 1, 1, 1, 1]
于 2013-02-07T07:00:09.950 に答える
2
それを行うには、任意の並べ替えアルゴリズムを使用します。初心者の場合はバブルソートを使用します（理解しやすい）Wiki
を参照してください
public static void bubble_srt( int a[], int n ){
int i, j,t=0;
for(i = 0; i < n; i++){
for(j = 1; j < (n-i); j++){
if(a[j-1] > a[j]){
t = a[j-1];
a[j-1]=a[j];
a[j]=t;
}
}
}
}
@Pradeep
が言ったように編集：あなたは間違いなくArray.sort（）を使うかもしれません
于 2013-02-07T06:59:52.507 に答える
1
クラスのArrays.sortメソッドを使用できます。Arrays
int[] A = {0,1,1,0,1,0,1,1,0};
Arrays.sort(A);
System.out.println(A);
于 2013-02-07T07:00:42.243 に答える
1
実際には、標準の既製の並べ替えアルゴリズムは通常、O（n * log（n））で機能します。すべての値（つまり、1の数）を追加したら、配列を実行するだけで済みます。これをに入れたとしましょうcount1。次に、最初の位置を1に設定し、残りを0に設定して、配列をもう一度確認しcount1ます。2nステップかかります。
もちろん、他のポスターが言っているように、この種の最適化は、ボトルネックを検出した後に行うことであり、開始時にすぐに行うことではありません。
于 2013-02-07T07:05:49.553 に答える
0
Arrays.sort（A、Collections.reverseOrder（））;
于 2013-02-07T07:03:06.413 に答える
0
使用する
Arrays.sort(A);
配列をソートするメソッド。
于 2013-02-07T07:04:56.747 に答える
0
あなたもこのように試すことができます
public static void main(String[] args) {
int inputArray[] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0 };
formatInputArray(inputArray);
}
private static void formatInputArray(int[] inputArray) {
int count = 0;
for (int i = 0; i < inputArray.length; i++) {
if (inputArray[i] == 0) {
count++;
}
}
// System.out.println(count);
for (int i = 0; i < inputArray.length; i++) {
if (i < count) {
inputArray[i] = 0;
}
else {
inputArray[i] = 1;
}
}
for (int i = 0; i < inputArray.length; i++) {
System.out.print(inputArray[i] + " , ");
}
}
于 2017-08-16T08:50:12.163 に答える
0
0、1、2のみを含む配列をソート
import java.util.*;
public class HelloWorld {
static void sort012(int []a, int length) {
int start = 0;
int mid = 0;
int end = length - 1;
int temp;
while(mid<=end) {
switch(a[mid]) {
case 0:
temp = a[start];
a[start] = a[mid];
a[mid] = temp;
start++;
mid++;
break;
case 1:
mid++;
break;
case 2:
temp = a[end];
a[end] = a[mid];
a[mid] = temp;
end--;
break;
}
}
}
public static void main(String []args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i =0;i<n; i++)
a[i] = sc.nextInt();
HelloWorld.sort012(a, n);
// Print the sorted Array
for (int i =0;i<n; i++)
System.out.println(a[i]);
}
}
于 2018-07-24T13:43:03.960 に答える
0
var binaryArr = [1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0];
//i - starting index
//j - ending index
function binarySort(arr){
var i=0,j=arr.length-1;
for(;i!=j;){
if(arr[i] == 1){
if(arr[j] == 0){
arr[i] = 0;
arr[j] = 1;
j--;
i++;
} else {
j--;
}
}else{
i++;
}
}
}
binarySort(binaryArr);
于 2018-10-23T13:13:56.897 に答える
0
Team
Please consider the below program in Swift in o(n) time complexity and constant extra space.
import UIKit
var inputArray = [1,0,1,0,0,0,0,1,1,1,1,1,1]
var leftIndex: Int = 0
var rightIndex: Int = inputArray.count-1
while leftIndex < rightIndex{
while inputArray[leftIndex] == 0 && leftIndex < rightIndex{
leftIndex = leftIndex+1
}
while inputArray[rightIndex] == 1 && rightIndex > leftIndex {
rightIndex = rightIndex-1
}
if leftIndex < rightIndex{
inputArray[leftIndex] = 0
inputArray[rightIndex] = 1
leftIndex = leftIndex+1
rightIndex = rightIndex-1
}
}
print(inputArray)
于 2019-01-27T07:39:46.217 に答える
0
以下のコードを使用して、0と1の配列を並べ替えます。
public static int[] sortArray(int[] array){
int first = 0;
int last = array.length-1;
while(first<last){
if(array[first]==0){
first++;
}else if(array[last] == 0){
int temp = array[last];
array[last] = array[first];
array[first] = temp;
first++;
}else{
last--;
}
}
return array;
}
于 2020-06-19T11:02:09.227 に答える
0
public static void sort(int a[]) {
int sum=0;
int b[]= new int [a.length];
for(int i=0;i<a.length;i++) {
sum=sum+a[i];
}
System.out.println(sum);
int j=b.length-1;
while(sum>0) {
b[j]=1;
sum--;
j--;
}
System.out.println(Arrays.toString(b));
}
于 2020-08-12T15:20:27.353 に答える
0
次のコードは、配列を並べ替えます。その場でそうすることに注意してください-新しいオブジェクトを返すのではなく、メモリ内のオブジェクトを変更します。
Pythonの場合
arr=[0,1,0,0,1,1,1,0,1,1,0]
arr.sort()
print(arr)
Javaの場合
public class test{
public static void main(String[] args){
int[] arr= {0,1,0,0,1,1,1,0,1,1,0};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}}
于 2021-06-15T08:36:50.293 に答える
0
public class Test {
public static void main(String[] args) {
int[] arr = {0, 1, 0, 1, 0, 0, 1, 1, 1, 0};
int start = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
arr[start] = 0;
if (i != start) { // should not override same value with 1
arr[i] = 1;
}
start++;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
//複雑さはO（n）
于 2021-07-07T04:00:05.623 に答える
-1
int [] a = {0,1,1,0,1,0,1,1,0}
ここでは、iを1から開始するiで反復処理しているため、以前のインデックス値を現在のiの値と比較できます。配列をソートするためにスワッピング技術を使用しました。
注： Sort/2ポインター手法も使用できます。
public int[] sort(int[] a){
int temp=0;
for(int i=1;i<a.length;i++){
if( a[i-1] > a[i]){
temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
}
}
return a[i];
}
時間計算量：O（n）
于 2021-05-23T13:38:00.573 に答える