旋转数组 k 次。

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

Rotate Array by k

问题

给定一个数组和一个数字 k,我们需要将数组旋转 k 次。

示例输入
1            // 测试用例数量
5 2          // 5(数组大小)2(旋转次数)
1 2 3 4 5    // 数组元素
示例输出
4 5 1 2 3

以下是您的代码:

import java.util.*;
class TestClass {
    public static void main(String args[] ) throws Exception {
        // 在这里编写您的代码
        Scanner input=new Scanner(System.in);
        int testcases=input.nextInt();

        for(int i=0;i<testcases;i++)
        {
            int size=input.nextInt();
            int rotationNo=input.nextInt();
            rotateArray(size, rotationNo, input);
        }
    }
    public static void rotateArray(int size, int rotationNo, Scanner input)
    {
        int[] arr=new int[size];
        int[] result=new int[size];

        rotationNo=rotationNo%size;

        for(int i=0;i<size;i++)
        {
            arr[i]=input.nextInt();
        }

        int resultIndex=0;

        int index=size-rotationNo;

        int k=index,t=0,track=0;

        while(true)
        {
            if(k<size)
            {
                System.out.print(arr[k++]+" ");
                ++track;

                if(track==size)
                {
                    break;
                }
                else
                {
                    continue;
                }
            }
            if(t<index)
            {
                if(t==(index-1))
                {
                    System.out.print(arr[t++]);
                }
                else
                {    
                    System.out.print(arr[t++]+" ");
                }
                ++track;
                
                if(track==size)
                {
                    break;
                }
                else
                {
                    continue;
                }
            }
        }

        System.out.println();
    }
}

这个问题是在编程竞赛中提出的。除了一个显示超时的测试用例外,我的所有测试用例都通过了。但是我不明白超时的原因。无论测试用例是什么,循环都会在有限时间内停止。我的代码的时间复杂度是 O(n)。是否有其他更好、更有效的解决方案?

英文:

Given an array and a number k we have to rotate array k times.

Sample Input
1            //number of of testcases 
5 2          //5(array size) 2(K value)
1 2 3 4 5    /array elements
Sample output
4 5 1 2 3

Here is my code

import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
// Write your code here
Scanner input=new Scanner(System.in);
int testcases=input.nextInt();
for(int i=0;i<testcases;i++)
{
int size=input.nextInt();
int rotationNo=input.nextInt();
rotateArray(size, rotationNo, input);
}
}
public static void rotateArray(int size, int rotationNo, Scanner input)
{
int[] arr=new int[size];
int[] result=new int[size];
rotationNo=rotationNo%size;
for(int i=0;i<size;i++)
{
arr[i]=input.nextInt();
}
int resultIndex=0;
int index=size-rotationNo;
int k=index,t=0,track=0;
while(true)
{
if(k<size)
{
System.out.print(arr[k++]+" ");
++track;
if(track==size)
{
break;
}
else
{
continue;
}
}
if(t<index)
{
if(t==(index-1))
{
System.out.print(arr[t++]);
}
else
{    
System.out.print(arr[t++]+" ");
}
++track;
if(track==size)
{
break;
}
else
{
continue;
}
}
}
System.out.println();
}
}

This question was asked in a programming competition. My all testcases were passing except one which showed time limit exceeded. But I am not understanding what is the cause of time limit exceed. Loops will always halt whatever be the testcase.
Time Complexity of my code is O(n).
Is there another better and efficient solution?

答案1

得分: 1

开始在读取并存储了k个值后直接输出输入(即不存储它),然后输出最初读取并存储的k个值。

数组内的移位操作在这里是相关的操作。所做的移位越少(如果正确实现的话,移位的距离实际上不是很重要),越好。这包括了与数组的存储和检索有关。我认为读取和输出,如果在其中没有任何处理,可以忽略不计。也就是说,我关注移位操作。

严格来说,读取和输出是一种处理,这意味着不能计算出O()的任何改进。

但请允许我在估算改进的O()时忽略读取和输出:

所提出的建议将改进从O(n)到O(k)的移位期间的数组访问次数。可以承认在这里忽略了读取和输出。在这里避免了从数组存储和检索以及尤其是在数组内的移位操作,这就是这里相关的O(k)部分。
因此,相关操作是O(k),在O(1)中忽略了n-k个值。

像这样的一个测试案例:

1
10000 1
1 2 3 4 5 6 7 8 ...

将很容易淘汰那些在读取之后,在输出之前执行'O(410000)'的程序,即为了移位而存储全部内容,然后为了输出再次读取全部内容。与仅存储单个值并在最后再次读取以进行输出的'O(21)'相比。
(是的,我知道干净的O()分析不使用系数或任何数字。但我希望你能理解我的观点。;-)

这里是一个代码建议(简化为一个单一的测试案例):

import java.util.*;
public class Test {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int testcases= input.nextInt(); //忽略,假设为1
        int size     = input.nextInt();
        int rotation = input.nextInt();
        int i=0;

        int[] newArr = new int[rotation%size]; //小数组
        // 基于User-Upvotedon'tsayThanks提出的好主意

        for(; i<rotation%size; i++)
        {
            newArr[i] = input.nextInt(); //很少的写入访问
        }
        for(; i<size; i++)
        {
            System.out.println( input.nextInt()); //许多直接输出
        }
        for(i=0; i<rotation%size; i++)
        {
            System.out.println(newArr[i]); //从数组中输出很少的内容
        }
        return;
    }
}

对于以下输入:

1
5 2
1 2 3 4 5

它会给出以下输出:

3
4
5
1
2

对于需要模数的输入,输出是相同的:

1
5 7
1 2 3 4 5
英文:

Start outputting the input directly (i.e. without storing it) as soon as k values have been read and stored.
Then output the k initially read and stored values.

The shifting inside the array, is the relevant operation here.
The fewer shifts are done (the distance of shifting is not really relevant here, if implemented correctly), the better. It includes the storing and retrieving to/from an array. I consider the reading and outputting, if done without any processing in between, to be negligible. I.e. I focus on the shifting.

Strictly speaking, the reading and outputting is processing and that would mean that no improvement of O() can be calculated.

But allow me to ignore the reading and outputting for an O() estimation of the improvement:

The proposed recommendation will improve the number of array-accesses during shifting from O(n) to O(k). Admittedly the reading and outputting is ignored here. Storing and retrieving from an array and especially the shifting inside the array is avoided here and that is the O(k) part which is relevant here.
So the relevant operations are O(k), ignoring n-k values in O(1).

A test case like

1
10000 1
1 2 3 4 5 6 7 8 ...

will easily eliminate programs which after reading and before outputting, do O(4*10000), i.e. store all, read and write all for shifting and then read all for outputting. Compared to O(2*1) for only storing a single value and reading again for outputting at the end.
(Yes, I know clean O() analysis does not use factors, or any digits. You stil get the point, I hope. 旋转数组 k 次。

Here is a code proposal (simplified to a single testcase):

import java.util.*;
public class Test {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int testcases= input.nextInt(); //ignored, assuming 1
        int size     = input.nextInt();
        int rotation = input.nextInt();
        int i=0;

        int[] newArr = new int[rotation%size]; //small array
        // based on the nice idea by User-Upvotedon'tsayThanks
        
        for(; i<rotation%size; i++)
        {
            newArr[i] = input.nextInt(); // few write accesses
        }
        for(; i<size; i++)
        {
            System.out.println( input.nextInt()); //many direct outpots
        }
        for(i=0; i<rotation%size; i++)
        {
            System.out.println(newArr[i]); // few outputs from array
        }
        return;
    }
}

For an input of:

1
5 2
1 2 3 4 5

It gets you an output of:

3
4
5
1
2

Same output for a modulo-requiring input of:

1
5 7
1 2 3 4 5

答案2

得分: 0

以下是您提供的代码的中文翻译部分:

我提供了下面的解决方案它将直接输出扫描仪输入直到达到输入的大小为止它对输入具有恒定的时间复杂度O(n)但只触摸每个项目一次并避免使用可能会增加迭代次数的while循环

public class Test {

    public static void main(String[] args) {

        int rotation = new Scanner(System.in).nextInt();
        int size = new Scanner(System.in).nextInt();

        int[] values = rotate(rotation, size, new Scanner(System.in));

        for(int i : values){
            System.out.println(i);
        }
    }

    public static int[] rotate(int rotation, int size, Scanner input){

        int[] newArr = new int[size];

        for(int i = 0; i<size; i++){

            int newPosition = i + rotation;

            newPosition = newPosition >= size ? newPosition - size : newPosition;

            newArr[newPosition] = input.nextInt();

        }

        return newArr;
    }
}

请注意,这只是代码的翻译部分。

英文:

I have provided a solution below which will directly output the scanner input up until the size of input has been met. It has a constant time o(n) for input, however it only touches each item once. and avoids the use of a while loop that may otherwise increase the multiplier of the iterations.


public class Test {
public static void main(String[] args) {
int rotation = new Scanner(System.in).nextInt();
int size = new Scanner(System.in).nextInt();
int[] values = rotate(rotation, size, new Scanner(System.in));
for(int i : values){
System.out.println(i);
}
}
public static int[] rotate(int rotation, int size, Scanner input){
int[] newArr = new int[size];
for(int i = 0; i&lt;size; i++){
int newPosition = i + rotation;
newPosition = newPosition &gt;= size ? newPosition - size : newPosition;
newArr[newPosition] = input.nextInt();
}
return newArr;
}
}

huangapple
  • 本文由 发表于 2020年8月15日 13:49:32
  • 转载请务必保留本文链接:https://go.coder-hub.com/63423021.html
匿名

发表评论

匿名网友

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

确定