package test;
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;
/**
* Created by nemo_odissey on 10.07.2017 12:45 for <a href="https://toster.ru/q/440261?utm_source=email_notifications&utm_medium=email&utm_content=mention&utm_campaign=notifications#comment_1428657" >Какую сортировку применять?</a>.
*/
public class JapanEditor
{
/**
* Compare by frequence and if equal, compare lexicographically
*/
public static class ComparePrefixWithFreq implements Comparator
{
@Override
public int compare( Object obj1, Object obj2 )
{
int cmp = ((WordItem) obj2).count - ((WordItem) obj1).count; // compare in reverse frequencies
if ( cmp != 0 ) // texts are not equals
return cmp;
return((WordItem)obj1).word.compareTo( ((WordItem)obj2).word ); // if freqs are equal, compare lexicographically
}
}
/**
* Class to store vocabulary item and make it comparable only lexicographically
*/
public static class WordItem implements Comparable
{
public String word;
public int count;
public WordItem( String word, int count )
{
this.count = count;
this.word = word;
}
@Override
public int compareTo( Object obj )
{
return this.word.compareTo( ((WordItem)obj).word );
}
}
/**
* Обработки ошибок НЕТ
* @param args путь_к_файлу_с_данными, где хранится задание
* @throws IOException
*/
public static void main( String[] args ) throws IOException
{
long start = new Date().getTime();
BufferedReader brd = new BufferedReader( new FileReader(args[0]), 32 * 1024 );
// читаем число слов
int wordCnt = Integer.parseInt( brd.readLine() );
WordItem[] wordArr = new WordItem[wordCnt];
// Читаем все слова и их частоты
for(int i = 0; i < wordCnt; i++)
{
String[] elems = brd.readLine().split( " " );
wordArr[ i ] = new WordItem( elems[0], Integer.parseInt( elems[1] ) );
}
// сортируем массив словаря
Arrays.sort( wordArr );
// сортировщик по частоте
ComparePrefixWithFreq compareWithFrequence = new ComparePrefixWithFreq();
// считываем и обрабатываем каждый префикс один за другим
int prefCnt = Integer.parseInt( brd.readLine() );
System.out.printf( "Счётчик слов %d, счётчик префиксов %d\n", wordCnt, prefCnt );
System.out.printf( "Словарь считан и отсортирован за %,d млс.\n\n", new Date().getTime() - start );
int summaryWordCount = 0;
WordItem prefixItem = new WordItem( null, 1 );
for(int i = 0; i < prefCnt; i++)
{
String prefix = brd.readLine().trim();
prefixItem.word = prefix;
int pos = Arrays.binarySearch(wordArr, prefixItem ); // if positive, point to a word in vocabulary started from prefix or equal to it
if ( pos < 0) // no precise prefix value found in vocabulary
pos = -(pos + 1); // pos to the first element starting from prefix
if ( pos >= wordCnt) // префикс отсутствует в словаре
continue;
if ( wordArr[pos].word.startsWith( prefix )) // Если префикс есть, ищем его конец в словаре
{
char nextLastChar = prefix.charAt( prefix.length() - 1 );
prefixItem.word = prefix.substring( 0, prefix.length() -1 ) + (++nextLastChar); // готовим следующую не строку
int pos1 = Arrays.binarySearch( wordArr, pos, wordCnt, prefixItem ); // ищем последнее вхождение префикса в словаре
if ( pos1 < 0)
pos1 = -pos1;
if ( pos1 > wordCnt)
pos1 = wordCnt;
summaryWordCount += pos1 - pos;
// pos -> first word with prefix, pos1 -> first word without prefix
WordItem[] wordsWithPrefix = Arrays.copyOfRange( wordArr, pos, pos1 );
Arrays.sort( wordsWithPrefix, compareWithFrequence );
int wordWithPrefCnt = Math.min( wordsWithPrefix.length, 10 );
for( int j = 0; j < wordWithPrefCnt; j++ )
//System.out.printf("%s %d\n", item.word, item.count); // debug output
System.out.println( wordsWithPrefix[j].word );
System.out.println(""); // add empty line according to the task requirements
}
}
brd.close();
System.out.printf( ">>> Длительность обработки %,d млс., средний размер выборки по каждому префиксу %d\n", new Date().getTime() - start, summaryWordCount / prefCnt);
}
}
package ru.ts.common.records;
/**
* Utility methods for packing/unpacking primitive values in/out of bytes and
* integer arrays using <b>big-endian</b> byte ordering.
*/
public class Bits
{
/*
* Methods for unpacking primitive values from byte arrays starting at given
* offsets.
*/
public static boolean getBoolean(byte[] b, int off)
{
return b[ off ] != 0;
}
static int[] BYTE_MASK;
static int[] BYTE_SHIFT;
static
{
BYTE_MASK = new int[] { 0xFF, 0xFF00, 0xFF0000, 0xFF000000 };
BYTE_SHIFT = new int[] { 0, 8, 16, 24 };
}
static byte getByte(int[] b, int off, int ind)
{
return (byte)((b[ off ] & BYTE_MASK[ ind ]) >> BYTE_SHIFT[ ind ]);
}
static boolean getBoolean(int[] b, int off, int ind)
{
return ((b[ off ] & BYTE_MASK[ ind ]) >> BYTE_SHIFT[ ind ]) != 0;
}
public static char getChar(byte[] b, int off)
{
return (char) (((b[ off + 1 ] & 0xFF) << 0) + ((b[ off + 0 ] & 0xFF) << 8));
}
static int[] CHAR_MASK;
static int[] CHAR_SHIFT;
static
{
CHAR_MASK = new int[] { 0xFFFF, 0xFFFF0000 };
CHAR_SHIFT = new int[] { 0, 16 };
}
/**
*
* @param b bit array containing of char looked for
* @param off offset to the array
* @param ind index of char packed into int. May be 0 or 1 ONLY!!!
* @return character stored in the array
*/
public static char getChar(int[] b, int off, int ind)
{
return (char) ( (b[off] & CHAR_MASK[ind]) >> CHAR_SHIFT[ind]);
}
static short getShort(byte[] b, int off)
{
return (short) (((b[ off + 1 ] & 0xFF) << 0) + ((b[ off + 0 ] & 0xFF) << 8));
}
/**
* the same as char
* @param b
* @param off
* @param ind index of short packed into int may be 0 or 1 ONLY
* @return
*/
static short getShort(int[] b, int off, int ind)
{
return (short) ( (b[off] & CHAR_MASK[ind]) >> CHAR_SHIFT[ind] );
}
public static int getInt(byte[] b, int off)
{
return ((b[ off + 3 ] & 0xFF) << 0) + ((b[ off + 2 ] & 0xFF) << 8)
+ ((b[ off + 1 ] & 0xFF) << 16) + ((b[ off + 0 ] & 0xFF) << 24);
}
static int getInt(int[] b, int off)
{
return b[ off ];
}
static float getFloat(byte[] b, int off)
{
int i = ((b[ off + 3 ] & 0xFF) << 0) + ((b[ off + 2 ] & 0xFF) << 8)
+ ((b[ off + 1 ] & 0xFF) << 16) + ((b[ off + 0 ] & 0xFF) << 24);
return Float.intBitsToFloat(i);
}
static float getFloat(int[] b, int off)
{
return Float.intBitsToFloat( b[off] );
}
static long getLong(byte[] b, int off)
{
return ((b[ off + 7 ] & 0xFFL) << 0) + ((b[ off + 6 ] & 0xFFL) << 8)
+ ((b[ off + 5 ] & 0xFFL) << 16)
+ ((b[ off + 4 ] & 0xFFL) << 24)
+ ((b[ off + 3 ] & 0xFFL) << 32)
+ ((b[ off + 2 ] & 0xFFL) << 40)
+ ((b[ off + 1 ] & 0xFFL) << 48)
+ ((b[ off + 0 ] & 0xFFL) << 56);
}
public static long getLong(int[] b, int off)
{
return ((long)b[ off ] & 0xFFFFFFFFL) + ( ((long)(b[ off + 1 ])) << 32L);
}
public static double getDouble(byte[] b, int off)
{
long j = ((b[ off + 7 ] & 0xFFL) << 0) + ((b[ off + 6 ] & 0xFFL) << 8)
+ ((b[ off + 5 ] & 0xFFL) << 16)
+ ((b[ off + 4 ] & 0xFFL) << 24)
+ ((b[ off + 3 ] & 0xFFL) << 32)
+ ((b[ off + 2 ] & 0xFFL) << 40)
+ ((b[ off + 1 ] & 0xFFL) << 48)
+ ((b[ off + 0 ] & 0xFFL) << 56);
return Double.longBitsToDouble(j);
}
public static double getDouble(int[] b, int off)
{
long j = ((long)b[ off ] & 0xFFFFFFFFL) + ( ((long)(b[ off + 1 ])) << 32L);
return Double.longBitsToDouble(j);
}
/*
* Methods for packing primitive values into byte arrays starting at given
* offsets.
*/
static void putBoolean(byte[] b, int off, boolean val)
{
b[ off ] = (byte) (val ? 1 : 0);
}
static void putBoolean(int[] b, int off, int ind, boolean val)
{
b[ off ] &= ~(BYTE_MASK[ind]);
b[ off ] |= (byte) (val ? 1 : 0) << BYTE_SHIFT[ind];
}
static void putByte(int[] b, int off, int ind, byte val)
{
b[ off ] &= ~(BYTE_MASK[ind]);
b[ off ] |= val << BYTE_SHIFT[ind];
}
static void putChar(byte[] b, int off, char val)
{
b[ off + 1 ] = (byte) (val >>> 0);
b[ off + 0 ] = (byte) (val >>> 8);
}
static void putChar(int[] b, int off, int ind, char val)
{
b[off] &= ~CHAR_MASK[ind];
b[off] |= ((short)val) << CHAR_SHIFT[ind];
}
static void putShort(byte[] b, int off, short val)
{
b[ off + 1 ] = (byte) (val >>> 0);
b[ off + 0 ] = (byte) (val >>> 8);
}
static void putShort(int[] b, int off, int ind, short val)
{
b[off] &= ~CHAR_MASK[ind];
b[off] |= val << CHAR_SHIFT[ind];
}
public static void putInt(byte[] b, int off, int val)
{
b[ off + 3 ] = (byte) (val >>> 0);
b[ off + 2 ] = (byte) (val >>> 8);
b[ off + 1 ] = (byte) (val >>> 16);
b[ off + 0 ] = (byte) (val >>> 24);
}
static void putInt(int[] b, int off, int val)
{
b[ off ] = val;
}
static void putFloat(byte[] b, int off, float val)
{
int i = Float.floatToIntBits(val);
b[ off + 3 ] = (byte) (i >>> 0);
b[ off + 2 ] = (byte) (i >>> 8);
b[ off + 1 ] = (byte) (i >>> 16);
b[ off + 0 ] = (byte) (i >>> 24);
}
static void putFloat(int[] b, int off, float val)
{
int i = Float.floatToIntBits(val);
b[ off ] = (i);
}
public static void putLong(byte[] b, int off, long val)
{
b[ off + 7 ] = (byte) (val >>> 0);
b[ off + 6 ] = (byte) (val >>> 8);
b[ off + 5 ] = (byte) (val >>> 16);
b[ off + 4 ] = (byte) (val >>> 24);
b[ off + 3 ] = (byte) (val >>> 32);
b[ off + 2 ] = (byte) (val >>> 40);
b[ off + 1 ] = (byte) (val >>> 48);
b[ off + 0 ] = (byte) (val >>> 56);
}
public static void putLong(int[] b, int off, long val)
{
b[ off ] = (int) (val & 0x00000000FFFFFFFFL);
b[ off + 1 ] = (int) ( val >>> 32);
}
public static void putDouble(byte[] b, int off, double val)
{
long j = Double.doubleToLongBits(val);
b[ off + 7 ] = (byte) (j >>> 0);
b[ off + 6 ] = (byte) (j >>> 8);
b[ off + 5 ] = (byte) (j >>> 16);
b[ off + 4 ] = (byte) (j >>> 24);
b[ off + 3 ] = (byte) (j >>> 32);
b[ off + 2 ] = (byte) (j >>> 40);
b[ off + 1 ] = (byte) (j >>> 48);
b[ off + 0 ] = (byte) (j >>> 56);
}
public static void putDouble(int[] b, int off, double val)
{
long j = Double.doubleToLongBits(val);
b[ off ] = (int) (j & 0xFFFFFFFFL);
b[ off + 1 ] = (int) (j >>> 32L);
}
}
Итак, самая первая позиция префикса найдена точно! Или префикса вообще нет! Если он есть, берём до 10 первых лексикографических, начинающихся с искомого префикса. Т.к. сортировать можно либо лексикографически, либо по мощности (частоте). Для поиска по префиксу подходит только лексикографическая сортировка, естественно.
Если в ответе требуется выводить ответ сортированный по мощности (этого в условии не уловил, похоже), т.е. частоте, то будем (всё равно) сортировать основной массив лексикографически, затем забирать все слова в массиве с префиксами, затем их сортировать и выдавать до 10 первых. Это и будет правильный ответ. Полагаю, на времени результата это не скажется никак.
Из интереса возьму Вашу тестовую выборку и завтра проверю. Спасибо за тренировку :o)
P.S. Ошибки возможны, тестировал на выборке в 10 слов и 5 префиксов. Это к слову о пользе тестирования.
P.P.S. Ошибка понятно, не учёл, если префикс лексикографически выше последнего слова в словаре. Это надо обрабатывать, как пустой результат, т.е. пропускать и переходить дальше, да!