Circular Array Rotation 时间限制已超出(TLE)

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

Circular Array Rotation Time Limit Exceeded(TLE)

问题

我真的很困惑为什么我的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 question - Link to Question
the first question 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&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

得分: 1

问题在这里

for(int i=0;i&lt;n-k;i++) //this loop you are using for storing input elements in array
    ar[i]=in.nextInt();

for(int i=0;i&lt;k;i++) // here you again taking the input you don&#39;t need this loop
    System.out.print(in.nextInt()+&quot; &quot;);

for(int i=0;i&lt;n-k;i++)
    System.out.print(ar[i]+&quot; &quot;);

你还需要将while循环中的条件从while(--t&gt;0)改为while(--t &gt;= 0)。应该是&gt;= 0,否则它将无法工作。另一种解决方法是使用后减量 while(t-- &gt; 0)

你正在尝试打印数组的右旋转。因此,你需要从索引n - k开始打印元素。然后你需要计算结束索引,即(n - k) + n,这是因为数组有n个元素。然后你可以像这样访问数组元素arr[i % n]

以下是完整的工作解决方案

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; i++)
                ar[i] = in.nextInt();
            
            for (int i = n - k; i &lt; n + (n - k); i++)
                System.out.print(ar[i % n] + &quot; &quot;);
            System.out.println();
        }
    }
}
英文:

Problem is here

for(int i=0;i&lt;n-k;i++) //this loop you are using for storing input elements in array
    ar[i]=in.nextInt();

for(int i=0;i&lt;k;i++) // here you again taking the input you don&#39;t need this loop
    System.out.print(in.nextInt()+&quot; &quot;);

for(int i=0;i&lt;n-k;i++)
    System.out.print(ar[i]+&quot; &quot;);

You also need to change the condition in while loop while(--t&gt;0) to while(--t &gt;= 0). It should be &gt;= 0 other wise it will not work. Other solution is to use post decrement while(t-- &gt; 0)

You are trying to print right rotation of the array. So you need to start printing the elements from index n - k. Then you need to calculate the end index it is (n - k) + n this is because array has n elements. Then you can access array elements like this arr[i % n].

Here is the complete working solution

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; i++)
                ar[i] = in.nextInt();
            
            for (int i = n - k; i &lt; n + (n - k); i++)
                System.out.print(ar[i % n] + &quot; &quot;);
            System.out.println();
        }
    }
}

答案2

得分: 1

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

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

在这里,我们只需要在倒数第二个空格,即第4个空格处拆分数组字符串。因此,可以通过仅拆分字符串一次来实现输出:
5 6 1 2 3 4
第一次拆分 - 5 6 + 空格 + 第二次拆分 - 1 2 3 4
这个逻辑对我起作用,所有的测试用例都通过了。

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

代码片段:

    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;
    }
}

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

发表评论

匿名网友

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

确定