space O(1) time O(n)

MaximizeMinDistance

    import java.util.Arrays;
    import java.util.List;
    
    /**
     * Created by pyq on 11/24/16.
     */
    /*
    We have an array of Integers. We want to reorder the elements in-place to have even numbers as far from each other as possible (i.e. we want to maximize the minimum distance between any two even numbers in the list). Note that we do not want to create a second array, and would like this to happen in the original array, in-place.
    
    For example:
    [5, 3, 5, 2, 3, 8]
    We can re-order the elements:
    [2, 3, 5, 5, 3, 8]
    
    or for the following list:
    [9, 2, 3, 4, 4]
    we can re-order to have:
    [2, 9, 4, 3, 4]
    
     */
    
    /*
        题目转换成 only contains two kinds of number [0,1] 好理解
    number of 0: a
    number of 1: b
    array.len = a + b
    
    ==> 怎样尽可能均匀分配 （生活问题）
    因为结果永远是首尾都有
    
    就转化成
    怎么分配 a - 1 个 0 和 b 个 1  ( last index position always put 0)
    
    这时候怎么平均分呢
    
    distanceAtLeast = (a + b - 1) / (a - 1);
    
    oneMoreCount =  (a + b - 1) % (a - 1);  //意思是部分distance可能比least 多 1
    
    
    1.  first loop to put all 0 to tail
    
    2.  swap every distanceAtLeast + 1 distance (from 0, swap oneMoreCount times)
    
    3.  swap every distanceAtLeast distance
    
    对于EooEooEooEoo => EoooEoooEooE
     */
    public class MaximizeMinDistance {
        /* return the same original array (with the modification) that is passed  to the method*/
        public  static int[] distantEvenNumbers(int[] array) {
            // color sort;
            int l = 0;
            int r = array.length; // leftmost position of even number
            while (l < r) {
                // move it to tail
                if (array[l] % 2 == 0) {
                    r--;
                    swap(array, l, r);
                } else {
                    l++;
                }
            }
    
            int oddCount = r;
            int evenCount = array.length - oddCount;
    
            // quick return, also avoid denominator to be 0
            if (evenCount == 1 || evenCount == array.length) {
                return array;
            }
    
            int numAtLeast = (array.length - 1) / (evenCount - 1);
            int oneMoreCount = (array.length - 1) % (evenCount - 1);
    
            int evenIndex = 0;
            // swap oneMoreCount times at every  numAtLeast + 1 index
            for (int i = 0; i < oneMoreCount; ++i)
            {
                swap(array, evenIndex, r);
                r++;
                evenIndex += numAtLeast + 1;
            }
            // update remaining (evenIndex is already at the next swap place)
            while (evenIndex < array.length - 1) {
                swap(array, evenIndex, r);
                r++;
                evenIndex += numAtLeast;
            }
            return array;
        }
    
        private static void swap(int[] a, int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    
        public static void main(String[] args) {
            int[] a = {1,1,1,1,0,0,0,0,1,1};
            distantEvenNumbers(a);
            System.out.println(Arrays.toString(a));
            int[] b = {5, 3, 5, 2, 3, 8};
            distantEvenNumbers(b);
            System.out.println(Arrays.toString(b));
            int[] c = {2, 9, 4, 3, 4};
            distantEvenNumbers(b);
            System.out.println(Arrays.toString(c));
            int[] d = {0,1,1,0,1,1,0,1,1,0,1,1};
            distantEvenNumbers(d);
            System.out.println(Arrays.toString(d));
            int[] e = {0,1,1,1};
            distantEvenNumbers(e);
            System.out.println(Arrays.toString(e));
            int[] f = {0,0,0,0,1};
            distantEvenNumbers(f);
            System.out.println(Arrays.toString(f));
        }
    }