Как отсортировать строку по номерам и порядковым номерам?

Question

Учитывая массив случайно расположенных строчных букв, прописных букв и цифр.

Как я могу отсортировать массив таким образом, чтобы все строчные буквы приходили до всех прописных букв, приходили перед всеми цифрами? Классы символов не должны быть в порядке в соответствующих разделах.

ДОЛЖЕН РАБОТАТЬ В O (n) времени и O (1) пространстве. Очевидно, нельзя использовать функцию сборки в сортировке.

Моей мгновенной реакцией является цикл через строку 3 раза, например, ниже.

var newArr = []; 

for x in oldArr 
    if x is lowercase 
     newArr.add(x) 

for x in oldArr 
    if x is uppercase 
     newArr.add(x) 

for x in oldArr 
    if x is number 
     newArr.add(x) 

Но это использует память O (n).

Answer 1

Чтобы использовать память O (1), вы должны делать свопы на месте. Чтобы сделать в O (n) время, вы должны сделать 2 пробега разбиения массива символов.

1) Сделать функцию подкачки, заменяющую 2 пункта с индексами я и дж массиве:

swap (a, i, j): 
    if i <> j: 
     tmp = a[i] 
     a[i] = a[j] 
     a[j] = a[i] 

2) Сделайте пробегает массив и поставить прописные буквы первого:

j = 0 
for i in range(0, len(oldArr)): 
    if oldArr[i] is lowercase: 
     swap(oldArr, i, j) 
     j++ 

3) Сделайте пробег над массивом и введите заглавные буквы после строчных букв:

for i in range(j, len(oldArr)): 
    if oldArr[i] is uppercase: 
     swap(oldArr, i, j) 
     j++ 

4) Если номер является единственным l eft для символов, вы ничего не можете сделать

Answer 2

Сортировка и подсчет Radix не выполняется в линейном режиме или использует постоянное пространство. Тем не менее, я нашел проблему голландского национального флага одинаковой и нашел решение. Ниже приведена ссылка и мой код. http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/ https://en.wikipedia.org/wiki/Dutch_national_flag_problem

var sortLowerUpperNumber = function(arr) { 

    var lower = 0;     // Index for lower case letter 
    var mid = 0;     // Index for upper case letter 
    var num = nums.length - 1;  // Index for number 

    while (mid <= num) { 
     switch(arr[mid]) { 
      case lowerCaseLetter: 
       swap(arr[low], arr[mid]) 
       low++; 
       mid++; 
       break; 
      case upperCaseLetter: 
       mid++; 
       break; 
      case number: 
       swap(arr[mid], arr[num]) 
       num--; 
       break; 
     } 
    } 
};