OfferUp

SwapWithA.java

    /**
    有一个数组，里面是26个字母，顺序是乱的，有个API叫做 swich_with_a(int pos), 这个方法的作用是调换pos位置上的字母和字母”a“的位置
   （无论”a”在哪里，这个方法会把“a“换到pos的位置）。让你实现把这26个字母排序，但是只能用到这个swith_with_a来调换位置。
    遇到一个char[i]有两个思路:1. 把char[i]换到出去，到它应该在的位置上去，但这样不能让char[i]本身是对的，走完一遍后结果还是不对
    2. 不管char[i]是什么，我只要把字母i + 'a'换进来，换到位置i上就行，这样就保证了那个位置的字母一定是对的
    */

    public char[] sortChar(char[] array) {
        // record each character's index
        int[] index = new int[26];
        for (int i = 0; i < array.length; i++) {
            index[array[i] - 'a'] = i;
        }
        // from index1, try to make each position i have correct character i + 'a'
        // we first swap a to this position i, then swap a with i + 'a'
        // remember to update the index of character
        for (int i = 1; i < array.length; i++) {
            // need to swap Index first, so that array[i] will not change
            swapIndex(index, array[i] - 'a');
            swapA(array, i);
            // need to swapA first so that index[i] won't change
            swapA(array, index[i]);
            swapIndex(index, i);
        }
        return array;
    }
    // swap the index of index[i] and index[0]
    private void swapIndex(int[] index, int i) {
        int temp = index[0];
        index[0] = index[i];
        index[i] = temp;
    }
    // swap character a with array[pos]
    private void swapA(char[] array, int pos) {
       // int indexA = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 'a') {
                //indexA = i;
                array[i] = array[pos];
                array[pos] = 'a';
                return ;
            }
        }
    }