Сортировка чисел от 1 до 999 999 999 в словах как строки

У вас есть один миллиард чисел и 51 миллиард символов - велика вероятность, что это вопрос с подвохом, так как в среднем на каждое число приходится 51 символ. Просуммируйте преобразование всех чисел и посмотрите, получается ли в сумме 51 миллиард.

Изменить: Сумма составляет 70 305 000 000 символов, так что это неправильный ответ.

НЕПРАВИЛЬНО !!!!!!!!! Я НЕПРАВИЛЬНО ПРОЧИТАЮ ПРОБЛЕМУ. Я думал, что это означает «какая последняя буква в последнем номере в алфавитном порядке»

что не так:

public class Nums {

// if overflows happen, switch to an BigDecimal or something
// with arbitrary precision
public static void main(String[] args) {
    System.out.println("last letter: " + lastLetter(1L, 51000000L);
    System.out.println("sum: " + sum(1L, 51000000L);
}    

static char lastLetter(long start, long end) {
   String last = toWord(start);
   for(long i = start; i < end; i++)
      String current = toWord(i);
      if(current.compareTo(last) > 1)
         last = current;

   return last.charAt(last.length()-1);
}

static String toWord(long num) {
   // should be relatively easy, but for now ...
   return "one";
}

static long sum(long first, long n) {
   return (n * first + n*n) / 2;
}
}

на самом деле не пробовал: / LOL

Важно отметить, что при повторении всех 100 миллиардов возможных чисел будет много совпадений и двойного счета. Важно понимать, что количество строк, начинающихся с «восьмерки», равно количеству чисел, начинающихся с «нин», «семь» или «шесть» и т. Д.

Для меня это требует динамического программное решение, в котором количество строк для десятков, сотен, тысяч и т. д. вычисляется и сохраняется в некоторой таблице поиска. Конечно, будут особые случаи: один против одиннадцати, два против двенадцати и т. Д.

Я обновлю это, если смогу получить быстрое работающее решение.

Вот что я бы сделал:

1. Создайте массив из 2997 строк: от «единицы» до «девятьсот девятисот тысяч», от «одной тысячи» до «девятисот девятьсот девяносто тысяч» и «один миллион» до » девятьсот девятьсот девяти миллионов ".
2. Сохраните следующее о каждой строке: длину (это, конечно, можно вычислить), целочисленное значение, представленное строкой, и некоторое перечисление, чтобы указать, являются ли они" единицами "," тысячами "или" миллионами " .
3. Отсортируйте 2997 строк по алфавиту.

Создав этот массив, легко найти все 999 999 999 строк в алфавитном порядке на основе следующих наблюдений:

1. Ничто не может следовать за строкой «единицы»
2. Либо ничего , или строка "единиц", может следовать за "Строка тысяч
3. За строкой «миллионы» может следовать ничего, строка «единиц», строка «тысячи» или строка «тысячи», а затем строка «единиц».

Построение слов в основном включает создание "слов" из одной или трех букв на основе этих 2997 токенов, следя за тем, чтобы порядок токенов составлял допустимое число в соответствии с приведенными выше правилами. Для конкретного "слова" следующее "слово" находится следующим образом :

1. Увеличьте "слово", добавив первый токен в алфавитном порядке, если возможно.
2. Если это невозможно, переместите крайний правый токен к следующему по алфавиту, если возможно.
3. Если это тоже невозможно, затем удалите крайний правый токен и переместите второй крайний правый токен к следующему по алфавиту, если это возможно.
4. Если это тоже невозможно, все готово.

На каждом шаге вы можете вычислить общую длину строки и сумму чисел, просто сохраняя два промежуточных итога.

jMonkeyEngine

Плюсы

• Использует Java; управляемая память, хорошо поддерживается во многих зрелых IDE (Eclipse, NetBeans и т. д.), очень портативна
• Хорошее сочетание высокого и низкого уровня
• Современный трехмерный граф сцены
• Построен на LWJGL ], очень зрелая и хорошо работающая игровая библиотека
• Очень легкий; не добавляет особых накладных расходов
• Встроенная загрузка 3D-модели в различных форматах.
• Встроенный современный трехмерный граф сцены на основе узлов.
• Простота использования.
• Открытый исходный код; постоянно развивается и улучшается.
• Включает отбраковку, проверку коллизий и т. д.
• Имеет возможность сохранять и читать собственный сверхкомпактный, сверхбыстрый формат двоичной модели.
• Полный список .

] Минусы

• Использует Java, поэтому компилирует JIT и поэтому может работать немного медленнее, чем C ++ и другие варианты.
• Hasn ' (не буду вдаваться в подробности создания этого) также нужен массив из тысяч последних букв last_letters [1000] (опять же не буду вдаваться в подробности создания этого, поскольку это еще проще, даже сотни d даже десятки y, кроме 10, что является n другим циклом, хотя последний из e через nin e ноль не имеет значения)

  uint32 sizes999[1000];
  
  uint64 totallen = 0;
  strlen_million = strlen("million");
  strlen_thousand = strlen("thousand");
  for (uint32 i = 0; i<1000;++i){
      for (uint32 j = 0; j<1000;++j){
          for (uint32 j = 0; j<1000;++j){ 
             total_len += sizes999[i]+strlen_million + 
                          sizes999[j]+strlen_thousand +
                          sizes999[k];
             if totallen == 51000000000 goto done;
             ASSERT(totallen <51000000000);//he claimed  51000000000 was not intermediate
          }
      }
  }
  done:
  

  // теперь используйте ijk, чтобы получить последнюю букву, используя last_letters999

  // думайте о i, j, k как о базах цифр 1000

  // если k = 0 & j == 0, то буква n миллио n

  // если только k = 0, то буква d thousan d

  // в противном случае используйте массив last_letters с

  // цифра единиц база 1000, то есть k, не равна нулю

  // для суммы чисел i, j, k - это цифры числа с основанием 1000, поэтому

  n = i*1000000 + j*1000 + k;
  

  // представляет число и используйте

  sum = n*(n+1)/2;
  

  , если вы нужно сделать это для числа, отличного от 51000000000, затем также вычислить sums_sizes999 и использовать это естественным образом.

  общий объем памяти: 0 (1000);

Честно говоря, я бы позволил СУБД, такой как SQL Server или Oracle, делать эту работу за меня.

1. Вставьте миллиард строк в индексированную таблицу.
2. Вычислите столбец длины строки.
3. ] Начните снимать X лучших записей за раз с помощью SUM, пока я не дойду до 51 миллиарда.

Возможно, сервер на какое-то время выйдет из строя, так как ему потребуется много операций ввода-вывода с диска, но в целом я думаю, что я может найти ответ быстрее, чем тот, кто напишет для этого программу.

Иногда клиент действительно хочет просто выполнить задачу, и ему все равно, какой модный шаблон проектирования или структуру данных вы использовали.

Код выигрывает ...

#!/bin/bash
n=0
while [ $n -lt 1000000000 ]; do
   number -l $n | sed -e 's/[^a-z]//g'
   let n=n+1
done | sort > /tmp/bignumbers
awk '
BEGIN {
    total = 0;
}
{
    l = length($0); 
    offset = total + l - 51000000000;
    print total " " offset
    if (offset >= 0) {
        c = substr($0, l - offset, 1);
        print c;
        exit;
    }
    total = total + l;
}' /tmp/bignumbers

Проверено для гораздо меньшего диапазона ;-). Требуется ОЧЕНЬ много дискового пространства, сжатая файловая система была бы, ммм, ценной, но не такой большой памятью.

Сортировка также имеет параметры для сжатия рабочих файлов, и вы можете использовать gzip для непосредственного сжатия данных.

Нет. самое быстрое решение.

Но оно работает.

Все строки будут начинаться с единицы, десяти, двух, двадцати , трех, тридцати, четырех и т. Д., Поэтому я начну с выяснения, как много в каждом из ведер. Тогда вы должны хотя бы знать, к какому ведру нужно присмотреться.

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

Вопрос касается эффективных данных хранение, а не манипуляции со строками. Создайте перечисление для представления слов. слова должны появляться в отсортированном порядке, чтобы, когда придет время сортировать, сравнение было простым. Теперь сгенерируйте список и отсортируйте его. используйте тот факт, что вы знаете, сколько длины каждое слово в сочетании с перечислением, чтобы добавить нужный вам символ.

Да, еще раз я, но совершенно другой подход.

Просто вместо того, чтобы хранить «один-одиннадцать-семь» слов, вы пишете сортировку, чтобы использовать это при сравнении.

Сырая java POC:

public class BillionsBillions implements Comparator {
    public int compare(Object a, Object b) {
        String s1 = (String)a; // "1234";
        String s2 = (String)b; // "1235";

        int n1 = Integer.valueOf(s1);
        int n2 = Integer.valueOf(s2);

        String w1 = numberToWords(n1);
        String w2 = numberToWords(n2);

        return w1.compare(w2);
    }

    public static void main(String args[]) {
        long numbers[] = new long[1000000000]; // Bring your 64 bit JVMs

        for(int i = 0; i < 1000000000; i++) {
            numbers[i] = i;
        }

        Arrays.sort(numbers, 0, numbers.length, new BillionsBillions());

        long total = 0;

        for(int i : numbers) {
            String l = numberToWords(i);
            long offset = total + l - 51000000000;

            if (offset >= 0) {
                String c = l.substring(l - offset, l - offset + 1);
                System.out.println(c);
                break;
            }
         }
    }
}

"numberToWords" оставлен в качестве упражнения для читателя.

странная, но забавная идея.

создать разреженный список длин чисел от 0 до 9, затем 10-90 по десяткам, затем 100, 1000 и т. Д. И т. Д. До миллиарда , индексы - это значение целой части, длина которой сохраняется.

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

тогда вы занимаетесь математикой только при перемещении чисел, вычисляя длину по таблица после суммирования для вашей суммы.

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

(Первая попытка ошиблась, но я оставлю это, потому что полезнее видеть ошибки на пути к решению чего-либо, чем просто окончательный ответ.)

I сначала сгенерирует строки от 0 до 999 и сохранит их в массиве с именемousandStrings. Элемент 0 - это "", а "" представляет собой пробел в приведенных ниже списках.

В настройкеousandString используется следующее:

Units: "" one two three ... nine

Teens: ten eleven twelve ... nineteen

Tens: "" "" twenty thirty forty ... ninety

НастройкаousandString выглядит примерно так:

thousandsString[0] = ""

for (i in 1..10)
   thousandsString[i] = Units[i]
end

for (i in 10..19)
   thousandsString[i] = Teens[i]
end

for (i in 20..99)
   thousandsString[i] = Tens[i/10] + Units[i%10]
end

for (i in 100..999)
   thousandsString[i] = Units[i/100] + "hundred" + thousandsString[i%100]
end

Затем я бы отсортировал этот массив по алфавиту .

Тогда, предполагая, что t1 t2 t3 - это строки, взятые изousandString, все строки имеют вид

t1

OR

t1 + миллион + t2 + тысяча + t3

OR

t1 + тысяча + t2

Чтобы вывести их в правильном порядке, я бы обработал отдельные строки, за которыми следуют миллионы строк, за которыми следует строка + тысячи строк.

foreach (t1 in thousandsStrings)

   if (t1 == "")
     continue;

   process(t1)

   foreach (t2 in thousandsStrings)
      foreach (t3 in thousandsStrings)
         process (t1 + "million" + t2 + "thousand" + t3)
      end
   end

   foreach (t2 in thousandsStrings)
       process (t1 + "thousand" + t2)
   end
end

где процесс означает сохранение предыдущей длины суммы, а затем добавление новой длины строки к сумме, и если новая сумма> = вашей целевой сумме, вы выплевываете результаты, и, возможно, возврат или выход из цикла, что бы ни делало вас счастливым.

=============================================== ======================

Вторая попытка, другие ответы были правильными, что вам нужно использовать 3k строк вместо 1k строк в качестве основы.

Начните с тысячиString сверху, но опустите пробел "" для нуля. Остается 999 элементов и вызывается эта uStr (строка единиц).

Создайте еще два набора:

tStr = the set of all uStr + "thousand"

mStr = the set of all uStr + "million"

Теперь создайте еще два объединения наборов:

mtuStr = mStr union tStr union uStr

tuStr = tStr union uStr

Порядок uStr, tuStr, mtuStr

Теперь цикл и логика здесь немного иначе, чем раньше.

foreach (s1 in mtuStr)
   process(s1)

   // If this is a millions or thousands string, add the extra strings that can
   // go after the millions or thousands parts.

   if (s1.contains("million"))
      foreach (s2 in tuStr)
         process (s1+s2)          

         if (s2.contains("thousand"))
            foreach (s3 in uStr)
               process (s1+s2+s3)
            end
         end
      end
   end

   if (s1.contains("thousand"))
      foreach (s2 in uStr)
         process (s1+s2)
      end
   end
end

У этих строк будет много-много общих префиксов - идеальный вариант использования для trie , что резко сократит использование памяти и, вероятно, также время работы.

У этого парня есть решение головоломки, написанное на Haskell. Очевидно, Майкл Боргвардт был прав, используя Trie для поиска решения.

Я бы отсортировал имена первых 20 целых чисел и имена десятков, сотен и тысяч, вычислил, сколько чисел начинается с каждого из них, и перейду оттуда.

Например, первые несколько - [восемь, восемнадцать, восемьсот, восемь миллионов, восемь тысяч, восемьдесят, одиннадцать,… .

Цифры, начинающиеся с «восьмерки», равны 8. С «восьмой сотней» - 800-899, 800,000-899,999, 800,000,000-899,999,999. И так далее.

Число букв в конкатенации слов от 0 (представленной пустой строкой) до 99 может быть найдено и просуммировано; это можно умножить на «тысячу» = 8 или «миллион» = 7, добавив для более высоких диапазонов. Значение 800-899 будет в 100 раз больше длины «восемьсот» плюс длина 0-99. И так далее.

Вам нужно сохранить всю строку в памяти?

Если нет, просто сохраните, сколько символов вы уже добавили. Для каждой итерации вы проверяете длину текстового представления следующего числа. Если он превышает n-ю букву, которую вы ищете, буква должна быть в этой строке, поэтому извлеките ее по индексу, распечатайте и остановите выполнение. В противном случае добавьте длину строки к количеству символов и перейдите к следующему числу.