Weekly challenge2 – DescendPrint3

By | January 18, 2015
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

Considering the string has millions of chars. We should optimize the solution.
This time, I didn’t use ArrayList, charAt() etc. Instead, only array is allowed.
A char has 16 bits, which means maximum size is 65536. Compared to millions of chars, assume 65536 is a small size. I use a CharCount class to store the count of a char. So, there are 65536 number of CharCount. Assume the input is char[] chs
Step1, count the char in chs[]. Store the value in CharCount[].
Step2, we assume there are many 0 counted chars, so we iterate charCount[] for one time, filter the 0 counted elements.
Step3, do median of median quicksort on CharCount[].
Step4, print result.

  1. package weeklychallenge1;
  2. /*
  3.  * Given a string, sort its chars by their number of
  4.  * appearance in descending order. e.g. input: abcbaa, output: aaabbc.
  5.  */
  6. public class DescendPrint2 {
  7.     /*
  8.      * Median of median quicksort on charCount[]
  9.      */
  10.     public static void quickSortCharCount(CharCount[] charCount, int lo, int hi) {
  11.         int i = lo;
  12.         int j = hi;
  13.         int pivot = findKthCharCount(charCount, lo, hi, (hi – lo + 2) >> 1);
  14.         while (i <= j) {
  15.             while (charCount[i].count > charCount[pivot].count) {
  16.                 i++;
  17.             }
  18.             while (charCount[j].count < charCount[pivot].count) {
  19.                 j–;
  20.             }
  21.             if (i <= j) {
  22.                 CharCount tmp = charCount[i];
  23.                 charCount[i] = charCount[j];
  24.                 charCount[j] = tmp;
  25.                 i++;
  26.                 j–;
  27.             }
  28.         }
  29.         if (lo < j)
  30.             quickSortCharCount(charCount, lo, j);
  31.         if (i < hi)
  32.             quickSortCharCount(charCount, i, hi);
  33.     }
  34.     /*
  35.      * Find the kth element in charCount[start,…,end]
  36.      */
  37.     public static int findKthCharCount(CharCount[] charCount, int start,
  38.             int end, int k) {
  39.         CharCount tmp = null;
  40.         if (end – start < 5) {
  41.             // Bubble sort arr[start,…,end] for k times, the arr[start] is the
  42.             // median
  43.             for (int count = 0; count < k; count++, start++) {
  44.                 for (int j = end; j > start; j–) {
  45.                     if (charCount[j – 1].count > charCount[j].count) {
  46.                         tmp = charCount[j – 1];
  47.                         charCount[j – 1] = charCount[j];
  48.                         charCount[j] = tmp;
  49.                     }
  50.                 }
  51.             }
  52.             start–;
  53.             return start;
  54.         }
  55.         int groupSize = (end – start + 1) / 5;
  56.         int subStart = 0, subEnd = 0;
  57.         for (int i = 0; i < groupSize; i++) {
  58.             subStart = start + i * 5;
  59.             subEnd = start + i * 5 + 4;
  60.             subEnd = (subEnd > end) ? end : subEnd;
  61.             int groupMedian = findKthCharCount(charCount, subStart, subEnd,
  62.                     (subEnd – subStart + 2) >> 1);
  63.             tmp = charCount[start + i];
  64.             charCount[start + i] = charCount[groupMedian];
  65.             charCount[groupMedian] = tmp;
  66.         }
  67.         return findKthCharCount(charCount, start, start + groupSize – 1,
  68.                 (groupSize + 1) >> 1);
  69.     }
  70.     public static void descendPrint3(char[] chs) {
  71.         final int MAX_CHAR_SIZE = 65535;
  72.         // Calculate count of each char
  73.         CharCount[] charCount = new CharCount[MAX_CHAR_SIZE];
  74.         for (int i = 0; i < MAX_CHAR_SIZE; i++) {
  75.             charCount[i] = new CharCount((char) i, 0);
  76.         }
  77.         for (int i = 0; i < chs.length; i++) {
  78.             charCount[chs[i]].count++;
  79.         }
  80.         // It is believed that there are many 0 count in charCount[].
  81.         // Move the char with 0 count to the right side.
  82.         int start = 0, end = MAX_CHAR_SIZE – 1;
  83.         while (start < end) {
  84.             while (charCount[start].count != 0 && start < end) {
  85.                 start++;
  86.             }
  87.             while (charCount[end].count == 0 && start < end) {
  88.                 charCount[end] = null;
  89.                 end–;
  90.             }
  91.             if (start < end) {
  92.                 charCount[start] = charCount[end];
  93.                 charCount[end] = null;
  94.                 start++;
  95.                 end–;
  96.             }
  97.         }
  98.         // Do median-of-median quicksort to charCount[0,…,start-1]
  99.         quickSortCharCount(charCount, 0, start – 1);
  100.         for (int i = 0; i < start; i++) {
  101.             for (int j = 0; j < charCount[i].count; j++) {
  102.                 System.out.print(charCount[i].ch);
  103.             }
  104.         }
  105.     }
  106.     public static void main(String[] args) {
  107.         String str = “abcccbbaaa”;
  108.         char[] chs = str.toCharArray();
  109.         descendPrint3(chs);
  110.     }
  111. }
  112. class CharCount {
  113.     char ch;
  114.     int count;
  115.     public CharCount(char ch, int count) {
  116.         this.ch = ch;
  117.         this.count = count;
  118.     }
  119. }