数组旋转超时(时间限制已达到)

huangapple go评论105阅读模式
英文:

Array rotation TLE (Time Limit Exceeded)

问题

我真的很困惑为什么我的Java代码不起作用,在Hacker Earth的Code Monks上显示TLE。
这是第一个问题MONK AND ROTATION的链接 - 问题链接

import java.util.Scanner;
class TestClass {
    static int[] ar = new int[100001];
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        byte t = in.nextByte();
        while (t-- > 0) {
            int n = in.nextInt();
            int k = in.nextInt() % n;
            for (int i = 0; i < n - k; i++)
                ar[i] = in.nextInt();
            for (int i = 0; i < k; i++)
                System.out.print(in.nextInt() + " ");
            for (int i = 0; i < n - k; i++)
                System.out.print(ar[i] + " ");
            System.out.println();
        }
    }
}

我不知道为什么会出现TLE,我认为可能有一些无限循环在进行。

网站上的问题是-

Monk and Rotation
Monk喜欢对数组执行不同的操作,因此作为HackerEarth School的校长,他分配了一个任务给他的新学生Mishki。 Mishki将获得一个大小为N的整数数组A和一个整数K,她需要将数组向右旋转K步,然后打印出结果数组。 由于她是学校的新生,请帮助她完成任务。

输入:
第一行将包含一个整数T,表示测试用例的数量。
对于每个测试用例:
1)第一行包含两个整数N和K,其中N是数组中的元素数,K表示旋转的步数。
2)接下来的一行包含N个以空格分隔的整数,表示数组A的元素。
输出:
打印所需的数组。

约束条件:

1 <= T <= 20
1 <= N <= 10^5
0 <= K <= 10^6
0 <= A[i] <= 10^6

示例输入

1

5 2

1 2 3 4 5

示例输出

4 5 1 2 3

解释

这里T为1,意味着一个测试用例。

表示数组中的元素数和表示旋转步数。

初始数组为:
在第一次旋转中,5将出现在第一个位置,所有其他元素将从它们当前的位置向前移动一个位置。现在,结果数组将是:

在第二次旋转中,4将出现在第一个位置,所有其他元素将从它们当前的位置向前移动一个位置。现在,结果数组将是:

时间限制:每个输入文件1.0秒
内存限制:256 MB
源代码限制:1024 KB

英文:

I am really confused why my java code is not working it is giving TLE on Code Monks on Hacker Earth.
Here is the link to the 1

import java.util.Scanner;
class TestClass {
    static int[] ar=new int[100001];
    public static void main(String args[] ){
        Scanner in=new Scanner(System.in);
        byte t=in.nextByte();
        while(t--&gt;0){
            int n=in.nextInt();
            int k=in.nextInt()%n;
                for(int i=0;i&lt;n-k;i++)
                    ar[i]=in.nextInt();
                for(int i=0;i&lt;k;i++)
                    System.out.print(in.nextInt()+&quot; &quot;);
                for(int i=0;i&lt;n-k;i++)
                    System.out.print(ar[i]+&quot; &quot;);
            System.out.println();
        }
    }
}

I don't know why is it giving TLE I think there is some infinite loop going.

the question at the site is-

Monk and Rotation
Monk loves to perform different operations on arrays, and so being the principal of HackerEarth School, he assigned a task to his new student Mishki. Mishki will be provided with an integer array A of size N and an integer K , where she needs to rotate the array in the right direction by K steps and then print the resultant array. As she is new to the school, please help her to complete the task.

Input:
The first line will consists of one integer T denoting the number of test cases.
For each test case:

  1. The first line consists of two integers N and K, N being the number of elements in the array and K denotes the number of steps of rotation.
  2. The next line consists of N space separated integers , denoting the elements of the array A.
    Output:
    Print the required array.

Constraints:

1&lt;=T&lt;=20
1&lt;=N&lt;=10^5
0&lt;=K&lt;=10^6
0&lt;=A[i]&lt;=10^6

Sample Input

1

5 2

1 2 3 4 5

Sample Output

4 5 1 2 3

Explanation

Here T is 1, which means one test case.

denoting the number of elements in the array and , denoting the number of steps of rotations.

The initial array is:
In first rotation, 5 will come in the first position and all other elements will move to one position ahead from their current position. Now, the resultant array will be

In second rotation, 4 will come in the first position and all other elements will move to one position ahead from their current position. Now, the resultant array will be

Time Limit: 1.0 sec(s) for each input file
Memory Limit: 256 MB
Source Limit: 1024 KB

答案1

得分: 3

我不确定你的解决方案是否正确,但尝试使用StreamTokenizer或BufferedReader替代Scanner。Scanner速度较慢,当你需要读取大量数据时可能会导致超时错误(TLE)。

英文:

I'm not sure about the correctness of your solution, but try to use StreamTokenizer or BufferedReader instead of Scanner. Scanner is too slow and may result in TLE when you need to read a lot of data.

答案2

得分: 3

减少对 System.in 和 System.out 的读写次数
看以下解决方案

Scanner scanner = new Scanner(System.in);
int noOfTestCases = scanner.nextInt();

for (int i = 0; i < noOfTestCases; i++) {
    int arraySize = scanner.nextInt();
    int noOfRotations = scanner.nextInt();
    noOfRotations = noOfRotations % arraySize;
    scanner.nextLine();
    String inputString = scanner.nextLine();
    String[] inputStringArray = inputString.split(" ");

    StringBuffer sb = new StringBuffer();

    for (int j = 0; j < arraySize; j++) {
        sb.append(inputStringArray[(arraySize + j - noOfRotations) % arraySize] + " ");
    }

    System.out.print(sb);
    System.out.println("");
}
英文:

Reduce the number of reads and writes from/to System.in and System.out.
Look at the following solution

        Scanner scanner = new Scanner(System.in);
        int noOfTestCases = scanner.nextInt();

        for (int i = 0; i &lt; noOfTestCases; i++) {
            int arraySize = scanner.nextInt();
            int noOfRotations = scanner.nextInt();
            noOfRotations = noOfRotations % arraySize;
            scanner.nextLine();
            String inputString = scanner.nextLine();
            String[] inputStringArray = inputString.split(&quot; &quot;);

            StringBuffer sb = new StringBuffer();

            for (int j = 0; j &lt; arraySize; j++) {
                sb.append(inputStringArray[(arraySize + j - noOfRotations) % arraySize] + &quot; &quot;);
            }

            System.out.print(sb);
            System.out.println(&quot;&quot;);
        }

答案3

得分: 2

import java.util.*;
public class temp {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int p = 0;
            int ar[] = new int[n];
            for (int i = 0; i < n; i++) {
                ar[i] = sc.nextInt();
            }
            k %= n;
            for (int i = 0; i < n; i++) {
                p = ar[(i + (n - k)) % n];
                System.out.print(p + " ");
            }
            System.out.println();
        }
    }
}
英文:
import java.util.*;
public class temp {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t--&gt;0){
            int n = sc.nextInt();
            int k = sc.nextInt();
            int p = 0;
            int ar[] = new int[n];
            for(int i=0;i&lt;n;i++){
			    ar[i] = sc.nextInt();
		    }
            k %= n;
            for(int i=0;i&lt;n;i++){
                p = ar[(i+(n-k))%n];
                System.out.print(p+&quot; &quot;);
            }
            System.out.println();
        }		
	}
}

Though I have not used a big sized array in the starting, this code is working fine for all test cases.

Try this one.

答案4

得分: 1

从不同的角度来思考。与其将字符串拆分并转换为数组,然后应用迭代逻辑,我们可以应用不同的逻辑。

关键是,你只需要找到输入字符串的位置,我们只需要拆分一次。
我的意思是,<br/>
输入 => <br/>
6 2 &emsp; &emsp; &emsp; // 4是数字的长度,2是旋转的索引 <br/>
1 2 3 4 5 6 &emsp; &emsp; // 数组(使用缓冲读取器将输入作为字符串)

在这里,我们只需要在倒数第2个空格处拆分数组字符串,即第4个空格处。因此,只需拆分字符串一次即可获得输出 - <br/>
5 6 1 2 3 4<br/>
第一次拆分- 5 6 + 空格 + 第二次拆分- 1 2 3 4 <br/>
这个逻辑对我起作用,所有测试案例都通过了。

还要注意涵盖当数组输入字符串只有一个数字的特殊情况。

代码片段-

int count=0;
for(int k=0; k&lt;arr.length(); k++) {
    if(arr.charAt(k)==' ')
        count++;
    if(count==size-rot) {
         System.out.println(arr.substring(k+1,arr.length())
             + " " + arr.substring(0,k));
         break;
    }
}
英文:

Think from a different perspective. Instead of splitting the string and converting it into an array and applying the iterative logic, we can apply a different logic.

The trick is you just need to find the position of the input string where we have to split only once.
By that I mean,<br/>
input=><br/>
6 2 &emsp; &emsp; &emsp; //4 is the length of numbers and 2 is the index of rotation<br/>
1 2 3 4 5 6 &emsp; &emsp; //array (take input as a string using buffered reader)

Here, we just need to split the array string at the 2nd last space i.e. 4th space. So the output can be achieved by just splitting the string once-<br/>
5 6 1 2 3 4<br/>
first split- 5 6 + space + second split- 1 2 3 4 <br/>
This logic worked for me and all the test cases passed.

Also don't forget to cover the corner case scenario when array input string is just one number.

Code Snippet-

int count=0;
for(int k=0; k&lt;arr.length(); k++) {
    if(arr.charAt(k)==&#39; &#39;)
        count++;
    if(count==size-rot) {
         System.out.println(arr.substring(k+1,arr.length())
             + &quot; &quot; + arr.substring(0,k));
         break;
    }
}

答案5

得分: 0

问题出在for循环内部的System.out.print()调用。这是一个相当沉重的调用,如果调用次数过多,会产生额外的开销。这个解决方案有效:

//导入Scanner和其他实用程序类
import java.util.*;

class TestClass {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String input = s.nextLine();
        int noOfTests = Integer.parseInt(input);
        for (int t = 0; t < noOfTests; t++) {
            input = s.nextLine();
            String[] str = input.split(" ");
            int sizeOfArray = Integer.parseInt(str[0]);
            int noOfRotations = Integer.parseInt(str[1]);
            String strIntegerArray = s.nextLine();
            String[] array = strIntegerArray.split(" ");
            printRightRotatedArray(array, noOfRotations, strIntegerArray.length());
        }
    }

    static void printRightRotatedArray(String[] array, int noOfRotations, int lengthOfStr) {
        int len = array.length;
        int noOfAcutalRotations = noOfRotations % len;
        int startingIndex = len - noOfAcutalRotations;
        StringBuilder sb = new StringBuilder(lengthOfStr+1);
        for (int i = 0; i < len; i++) {
            sb.append(array[(startingIndex + i) % len]);
            sb.append(" ");
        }
        System.out.println(sb);
    }
}
英文:

Problem is in the System.out.print() call that is inside the for-loop. Thats a fairly heavy call and if called too many times and creates an overhead. This solution works:

//import for Scanner and other utility classes
import java.util.*;

class TestClass {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String input = s.nextLine();
        int noOfTests = Integer.parseInt(input);
        for (int t = 0; t &lt; noOfTests; t++) {
            input = s.nextLine();
            String[] str = input.split(&quot; &quot;);
            int sizeOfArray = Integer.parseInt(str[0]);
            int noOfRotations = Integer.parseInt(str[1]);
            String strIntegerArray = s.nextLine();
            String[] array = strIntegerArray.split(&quot; &quot;);
            printRightRotatedArray(array, noOfRotations, strIntegerArray.length());
        }
    }

    static void printRightRotatedArray(String[] array, int noOfRotations, int lengthOfStr) {
        int len = array.length;
        int noOfAcutalRotations = noOfRotations % len;
        int startingIndex = len - noOfAcutalRotations;
        StringBuilder sb = new StringBuilder(lengthOfStr+1);
        for (int i = 0; i &lt; len; i++) {
            sb.append(array[(startingIndex + i) % len]);
            sb.append(&quot; &quot;);
        }
        System.out.println(sb);
    }
}

答案6

得分: 0

putting all into string buffer and print at the end worked for me.

class TestClass {
    public static void main(String args[]) throws Exception {
        // BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder(); // 输出
        for (int i = 0; i < t; i++) {
            String[] nk = br.readLine().split(" ");
            int n = Integer.parseInt(nk[0]);
            int k = Integer.parseInt(nk[1]);
            String[] a = br.readLine().split(" ");
            int split = n - (k % n);
            for (int j = split; j < a.length; j++) {
                sb.append(a[j]);
                sb.append(' ');
            }
            for (int j = 0; j < split; j++) {
                sb.append(a[j]);
                sb.append(' ');
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}
英文:

putting all into string buffer and print at the end worked for me.

class TestClass {
public static void main(String args[] ) throws Exception {
    //BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();// output
    for(int i=0;i&lt;t;i++){
        String [] nk=br.readLine().split(&quot; &quot;);
        int n= Integer.parseInt(nk[0]);
        int k=Integer.parseInt(nk[1]);
        String [] a=br.readLine().split(&quot; &quot;);
        int split=n-(k%n);
        for (int j = split; j &lt; a.length; j++) {
            sb.append(a[j]);
            sb.append(&#39; &#39;);
        }
        for (int j = 0 ; j &lt; split; j++) {
            sb.append(a[j]);
            sb.append(&#39; &#39;);
        }
        sb.append(&quot;\n&quot;);
    }
    System.out.println(sb);
}
}

答案7

得分: 0

Scanner s = new Scanner(System.in);
int T = s.nextInt();
while(T > 0){
    int n = s.nextInt();
    int j = n - (s.nextInt() % n);
    s.nextLine();
    String [] arr = s.nextLine().split(" ");
    StringBuilder output = new StringBuilder();
    for(int i=j; i<n; i++){
        output.append(arr[i] + " ");
    }
    for(int i=0; i<j; i++){
        output.append(arr[i] + " ");
    }
    System.out.println(output);
    T--;
}
英文:
Scanner s = new Scanner(System.in);
    int T = s.nextInt();
    while(T&gt;0){
        int n = s.nextInt();
        int j = n - (s.nextInt() % n);
        s.nextLine();
        String [] arr = s.nextLine().split(&quot; &quot;);
        StringBuilder output = new StringBuilder();
        for(int i=j; i&lt;n; i++){
            output.append(arr[i] + &quot; &quot;);
        }
        for(int i=0; i&lt;j; i++){
            output.append(arr[i] + &quot; &quot;);
        }
        System.out.println(output);
        T--;
    }

huangapple
  • 本文由 发表于 2020年9月13日 03:45:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/63864284.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定