способы ускорить сортировку с полным подсчетом

Я столкнулся с вопросом на hackerrank. https://www.hackerrank.com/challenges/countingsort4

Моя первая попытка прошла все тестовые случаи, кроме последнего, из-за тайм-аута. После того, как не удалось придумать более эффективный алгоритм, я улучшил код, используя StringBuilder вместо прямого объединения строк. Это увеличило время работы с более чем 5 секунд до 3,5 секунд.

Мой вопрос в том, есть ли другой способ улучшить время работы? Спасибо.

Ниже приведен мой код.

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        scanner.nextLine();

        int[] oriNum = new int[N];        
        String[] oriStr = new String[N];
        int[] count = new int[100];
        int[] indices = new int[100];
        int[] output = new int[N];

        // save the originals and the count array
        for (int i = 0; i < N; i++) {
            oriNum[i] = scanner.nextInt();
            oriStr[i] = scanner.nextLine().trim();
            count[oriNum[i]]++;
        }

        // accumulate the count array
        indices[0] = 0;
        for (int i = 1; i < 100; i++) {
            indices[i] = indices[i-1] + count[i-1];
        }

        // output order
        for (int i = 0; i < N; i++) {
            int num = oriNum[i];
            output[indices[num]++] = i;
        }

        int bar = N/2;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {            
            int index = output[i];
            if (index < bar) 
                sb.append("- ");
            else 
                sb.append(oriStr[index]+ " ");
        }
        System.out.println(sb.toString());
    }
}

java optimization string-concatenation counting-sort
person Lei Chen    schedule 04.12.2014    source источник
comment
Вместо sb.append(oriStr[index]+); используйте sb.append(oriStr[index]).append();   -  person StanislavL    schedule 04.12.2014
comment
Этот вопрос кажется не по теме, потому что он запрашивает проверку кода и, как таковой, принадлежит Code Review SE.   -  person Boris the Spider    schedule 04.12.2014
comment
Если по какой-либо причине вы попали в эту тему во время поиска того, как сделать сортировку подсчета стабильной, как это требуется в упомянутом вопросе HackerRank, см. этот пост - Почему сортировка подсчетом является стабильной сортировкой?   -  person RBT    schedule 15.04.2018

Ответы (2)


arrow_upward
7
arrow_downward

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

person aioobe    schedule 04.12.2014
comment
Я попробовал BufferedReader, и время работы уменьшилось с 3,5 до 1,4 секунды. Отличное предложение, спасибо! - person Lei Chen; 04.12.2014
comment
Хех, пожалуйста. Я был в такой же ситуации. - person aioobe; 04.12.2014

arrow_upward
0
arrow_downward

Это был мой подход к проблеме. (это на С++).

void counting_sort(vector<int> &arr, int size,  vector<vector<string> > foo, vector<int> first_half)
{
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());

    int range = max - min + 1;

    int count[range] = {0};

    // counting frequency of numbers in array
    for (int i = 0; i < size; i++)
    {
        count[arr[i] - min]++;
    }

    // calculating cumulative sum
    for (int i = 1; i < range; i++)
    {
        count[i] += count[i - 1];
    }

    vector<vector<string> > output(size);

    // making the new sorted array
    for (int i = size - 1; i >= 0; i--) // traversing from backward for stability
    {
        output[count[arr[i]-min] - 1] = foo[i];
        count[arr[i]-min]--;
    }

    // copying the sorted array in original array
    int j=0;
    for (int i = 0; i < size; i++)
    {
        if(stoi(output[i][0]) == first_half[j])
        {
            cout << "- ";
            j++;
        }
        else
        {
            cout << output[i][1] << ' ';
        }
    }
}

// Complete the countSort function below.
void countSort(vector<vector<string>> arr) {

    vector<int> num;
    vector<int> first_half;
    for(int i=0; (unsigned)i<arr.size(); i++)
    {
        num.push_back(stoi(arr[i][0]));
        if(i < ((unsigned)arr.size()/2))
        {
            first_half.push_back(stoi(arr[i][0]));
        }
    }

    sort(first_half.begin(), first_half.end());
    counting_sort(num, num.size(), arr, first_half);
}
person Himanshu singh    schedule 18.10.2020