Завершено из-за тайм-аута в ранге хакера для больших входов

java arrays

1406 просмотра

1 ответ

1 Репутация автора

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

Джон Уотсон выполняет операцию, которая называется круговым вращением вправо на массиве целых чисел. После выполнения одной операции вращения вправо по кругу массив преобразуется из в.

Уотсон выполняет эту операцию раз. Чтобы проверить способность Шерлока идентифицировать текущий элемент в определенной позиции в повернутом массиве, Уотсон запрашивает запросы, где каждый запрос состоит из единственного целого числа, для которого вы должны напечатать элемент по индексу в повернутом массиве (т. Е. Значение из).

Формат ввода

Первая строка содержит разделенные пробелом целые числа,, и, соответственно. Вторая строка содержит разделенные пробелом целые числа, где каждое целое число описывает элемент массива (где). Каждая из последующих строк содержит одно целое число, обозначающее.

Ограничения

Выходной формат

Для каждого запроса выведите значение элемента по индексу повернутого массива в новой строке.

Пример ввода

3 2 3 1 2 3 0 1 2 Пример вывода

2 3 1

МОЙ КОД

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        int n,k,q,temp=0,c=0;
        Scanner sc=new Scanner(System.in);
        try{
        n=sc.nextInt();
        k=sc.nextInt();
        q=sc.nextInt();
        int[] arr=new int[n];
        int qrr[]=new int[q];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();
        while(sc.hasNext()){
            qrr[c++]=sc.nextInt();
        }
        for(int j=1;j<=k;j++){
        temp=arr[n-1];
        for(int i=n-2;i>=0;i--){
            arr[i+1]=arr[i];
        }
        arr[0]=temp;
        }
        for(int i=0;i<q;i++){
            System.out.println(arr[qrr[i]]);
        }
    }
    catch(Exception ae){
        System.out.println(ae.getMessage());
    }
}
}
Автор: Vaibhav Misra Источник Размещён: 18.07.2016 01:05

Ответы (1)


1 плюс

26 Репутация автора

import java.io.*;
import java.util.*;

public class Solution {

    public static int m,n,k,q,i=0,c=0;
    public static int errorflag = 0;
    public static int array[];
    public static int rotated[];
    public static Scanner in = new Scanner(System.in);

    public static int[] getArray(int n){
        array = new int[n];
        for(i=0;i<n;i++){
            array[i] = in.nextInt();
        }       
        return(array);
    }

    public static int[] rotate(int[] original){
        int[] rotated = new int[original.length];
        for(i=0;i<original.length;i++){
            rotated[(i+k)%original.length] = original[i];
        }
        return(rotated);
    }

Вышеуказанная функция работает с наихудшим случаем сложности O (n). По сути, вы назначаете новый индекс для элементов таким образом, чтобы они вращались вправо или увеличивались на величину k, а переполнение учитывалось операцией модуля.

    public static void main(String[] args) {
        n = in.nextInt();
        k = in.nextInt();
        q = in.nextInt();
        array = getArray(n);

        int m[] = new int[q];
        for(i=0;i<m.length;i++){
            m[i] = in.nextInt();
        }
        rotated = rotate(array);
        for(i=0;i<m.length;i++){
            System.out.println(rotated[m[i]]);
        }


    }
}
Автор: Abhikalp Unakal Размещён: 15.08.2016 10:20
Вопросы из категории :
32x32