最小値と最大値の配列を並べ替える

Question

配列がintの場合、最初の要素は最小値、2番目は最大値、3番目の最小値、4番目の最大値、4番目の最大値などを交互に並べ替える必要があります。 。私は完全にここに迷ってしまいました

...

Answer 1

場所での並べ替えは、元の配列をソートして、単一の新しい配列を作成することと同じように3つの別々の配列のスペースを必要としないが、のような複雑ではないん別の方法。そして、0番目のインデックスとソートされた配列の最後のインデックスから始まる新しい配列とポインタの現在のi番目のインデックスへのポインタで繰り返しを開始し。

public class Foo { 

    public static void main(String[] args) { 
     // Take your original array 
     int[] arr = { 1, 4, 5, 10, 6, 8, 3, 9 }; 
     // Use the Arrays sort method to sort it into ascending order (note this mutates the array instance) 
     Arrays.sort(arr); 
     // Create a new array of the same length 
     int[] minMaxSorted = new int[arr.length]; 
     // Iterate through the array (from the left and right at the same time) 
     for (int i = 0, min = 0, max = arr.length - 1; i < arr.length; i += 2, min++, max--) { 
      // the next minimum goes into minMaxSorted[i] 
      minMaxSorted[i] = arr[min]; 
      // the next maximum goes into minMaxSorted[i + 1] ... but 
      // guard against index out of bounds for odd number arrays 
      if (i + 1 < minMaxSorted.length) { 
       minMaxSorted[i + 1] = arr[max]; 
      } 
     } 
     System.out.println(Arrays.toString(minMaxSorted)); 
    } 
} 

Answer 2

ヒント：

二つの新しい配列を作成し、第一の順序をassentingにソートされ、他方が降順です。 2番目の配列から1番目の要素を選択し、1番目の配列から1番目の要素を選択するよりも、1番目と2番目の配列の半分になるまでこの選択を繰り返します。あなたはあなたの望む配列を得るでしょう。

希望すると、これが役立ちます。 @ Kaushal28の答えで

Answer 3

アプローチは、初心者のための最善のアプローチです。より多くのスペース（配列の2つの余分なコピー）が必要ですが、理解してコード化するのは簡単です。

高度なプログラマが一度配列をソートして、要素を再配置することを検討してください。それはうまくいくはずですが、ロジックは複雑です。

ヒント：あなたは "Clock Patience" を果たしていますか？

Answer 4

ここでもう一つの選択肢である：ソートされている指標を監視し、次の最小/最大のための残りを検索：

輸入java.util.Arraysは、 import java.util.Set;

/** 
* Demonstrates an option for sorting an int[] array as requested, 
* by keeping a list of the array indices that has been sorted, and searching 
* for the next min/max. 
* This code is not optimal nor robust. It serves a demo for this option only. 
* 
*/ 
public class AltSort { 

    //list of array elements that were sorted 
    static Set<Integer> indexSorted ; 

    public static void main (String[] args) throws java.lang.Exception  { 
     //test case 
     int[] array = new int[]{7,22,4,67,5,11,-9,23,48, 3, 73, 1, 10}; 
     System.out.println(Arrays.toString(altSort2(array))); 

     //test case 
     array = new int[]{ 1, 4, 5, 10, 6, 8, 3, 9 }; 
     System.out.println(Arrays.toString(altSort2(array))); 
    } 

    private static int[] altSort2(int[] array) { 

     if((array == null) || (array.length == 0)) { 
      System.err.println("Empty or null array can not be sorted."); 
     } 

     //returned array 
     int[] sortedArray = new int[array.length]; 

     //flag indicating wether to look for min or max 
     boolean lookForMin = true; 

     int index = 0; 
     while(index < array.length) { 

      if(lookForMin) { 
       sortedArray[index] = lookForArrayMin(array); 

      }else { 
       sortedArray[index] = lookForArrayMax(array); 
      } 

      index++; 
      //alternate look for min/look for max 
      lookForMin = ! lookForMin; 
     } 

     return sortedArray; 
    } 

    private static int lookForArrayMin(int[] array) { 

     int minValue = Integer.MAX_VALUE; 
     int minValueIndex = 0; 

     for(int i =0; i< array.length; i++){ 

      //if array[i] is min and was not sorted before, keep it as min 
      if((array[i]< minValue) && ! indexSorted.contains(i)) { 

       minValue = array[i]; //keep min 
       minValueIndex = i; //keep min index 
      } 
     } 

     //add the index to the list of sorted indices 
     indexSorted.add(minValueIndex); 
     return minValue; 
    } 

    private static int lookForArrayMax(int[] array) { 

     int maxValue = Integer.MIN_VALUE; //max value 
     int maxValueIndex = 0; //index of max value 

     for(int i =0; i< array.length; i++){ 

      //if array[i] is max and was not sorted before, keep it as max 
      if((array[i] > maxValue) && ! indexSorted.contains(i)) { 
       maxValue = array[i]; //keep max 
       maxValueIndex = i; //keep max index 
      } 
     } 

     //add the index to the list of sorted indices 
     indexSorted.add(maxValueIndex); 
     return maxValue; 
    } 
} 

Answer 5

この解決策は、Aaron Davisソリューションに基づいています。ループを簡単にするようにしました：

public class AltSort { 

    //list of array elements that were sorted 
    static Set<Integer> indexSorted = new HashSet<Integer>(); 

    public static void main (String[] args) throws java.lang.Exception 

    { 
     //test case 
     int[] array = new int[]{7,22,4,67,5,11,-9,23,48, 3, 73, 1, 10}; 
     System.out.println(Arrays.toString(altSort(array))); 

     //test case 
     array = new int[]{ 1, 4, 5, 10, 6, 8, 3, 9 }; 
     System.out.println(Arrays.toString(altSort(array))); 
    } 

    private static int[] altSort(int[] array) { 

     if((array == null) || (array.length == 0)) { 
      System.err.println("Empty or null array can not be sorted."); 
     } 

     Arrays.sort(array); 

     //returned array 
     int[] sortedArray = new int[array.length]; 
     int firstIndex = 0, lastIndex = array.length-1; 

     for (int i = 0; i < array.length; i++) { 

      if((i%2) == 0) { //even indices 

       sortedArray[i] = array[firstIndex++]; 
      } 
      else { 
       sortedArray[i] = array[lastIndex --]; 
      } 
     } 

     return sortedArray; 
    } 
}