Parition an Array

Question

給定一個整數數組找到將數組劃分爲兩個高數和低數的索引。例如[5，-1，3，8,6]，索引3將把數組分割爲[5，-1,3]和[8,6]，第二個分區中的所有數字都大於第一個。該解決方案必須在O（n）中工作。請建議如果這是正確的，並達到O（n）的複雜性。

private int calculateWinters(int[] a) { 
     System.out.println(partition(a, 0, a.length - 1)); 
     return partition(a, 0, a.length - 1); 

    } 

    int partition(int arr[], int low, int high) { 
     int pivot = arr[low]; 
     int i = low; // index of smaller element 
     int count = 0; 
     for (int j = low; j <= high; j++) { 
      // If current element is smaller than or 
      // equal to pivot 

      if (arr[j] <= pivot) { 

       i++; 
       i += count; 
       count = 0; 

      } else { 
       int temp = arr[j]; 
       arr[j] = pivot; 
       pivot = temp; 
       count++; 
      } 
     } 

     return i; 
    } 

Answer 1

public static void main(String[] args) { 
     Winters w = new Winters(); 
     int[] a = { 5, 4, 2, 10, 8, 78, 21, 2, 33 }; 
     w.calculateWinters(a); 

    } 

    private int calculateWinters(int[] a) { 
     System.out.println(partition(a, 0, a.length - 1)); 
     return partition(a, 0, a.length - 1); 

    } 

    int partition(int arr[], int low, int high) { 
     int pivot = arr[low]; 
     int i = low; // index of smaller element 
     List<Integer> list = new ArrayList<>(); 
     List<Integer> list1 = new ArrayList<>(); 
     while (arr[i] <= pivot) { 
      list1.add(arr[i]); 
      i++; 
     } 

     for (int k = i; k <= arr.length - 1; k++) { 
      list.add(arr[k]); 
      if (list1.size() > 1 && arr[k] < Collections.max(list1)) { 
       list1.addAll(list); 
       i = i + (k - i) + 1; 
      } 
     } 

     return i; 
    } 

} 

Answer 2

private int calculateWinters(int[] a) { 
      System.out.println(partition(a, 0, a.length - 1)); 
      return partition(a, 0, a.length - 1); 

     } 

     int partition(int arr[], int low, int high) { 
      int pivot = arr[low]; 
      int i = low; // index of smaller element 
      List<Integer> list = new ArrayList<>();// This is the list which will add all the numbers of an array which are smaller than pivot 
      List<Integer> list1 = new ArrayList<>();//This will contain all the number which are greater than the pivot 
      while (arr[i] <= pivot) { 
       list1.add(arr[i]); 
       i++; 
      } 

      for (int k = i; k <= arr.length - 1; k++) { 
       list.add(arr[k]);//adding all numbers greater than the pivot. 
//if we find any number smaller than the than the max of already encountered numbers, we will move the index(i) to the current pointer. 
       if (list1.size() > 1 && arr[k] < Collections.max(list1)) { 
        list1.addAll(list); 
        i = i + (k - i) + 1; 
       } 
      } 

      return i; 
     } 

    }