Java 中的块交换算法或数组旋转

2024 年 9 月 26 日 | 阅读 6 分钟

这是经常在 Google、Amazon、TCS、Accenture 等顶级 IT 公司面试中出现的非常有趣的问题。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将讨论 **Java 中的块交换算法和数组旋转**，并提供不同的方法和逻辑。此外，我们还将创建相应的 Java 程序。

数组旋转示例

输入

int arr[] = {7, 9, 8, 0, 5, 1, 6, 4}, s = 8, d = 2

输出：result[] = {8, 0, 5, 1, 6, 4, 7, 9}

解释：s 是输入数组的大小。d = 2 意味着我们需要旋转数组 2 次。第一次旋转后，我们得到：

{9, 8, 0, 5, 1, 6, 4, 7}。现在，我们再次旋转数组，得到以下结果：

让我们看另一个例子。

输入

int arr[] = {6, 8, 7, 9, 0, 5, 1, 3, 2, 4}, s = 10, d = 5

输出：result[] = {5, 1, 2, 3, 4, 6, 8, 7, 9, 0}

解释：旋转数组 5 次后，我们得到以下结果：

{5, 1, 2, 3, 4, 6, 8, 7, 9, 0}，这就是我们的答案。

块交换算法

在本节中，我们使用了块交换算法来旋转数组。请观察该算法：

步骤 1：将输入数组分成两个子数组，以 div 为分割点。令它们为 A = arr[0 ... div - 1] 和 B = arr[div ... n - 1]。

步骤 2：在 A 和 B 的大小相等之前，执行以下步骤：

如果 A 的大小大于 B，则将 A 分成两部分，A1 和 A2，使得 A1 的大小等于 A2。交换子数组 A1 和 B。这将使数组从 A1A2B 变为 BA2A1。
如果 B 的大小大于 A，则将 B 分成两部分，B1 和 B2，使得 B2 的大小与 B 的大小相同。交换子数组 A 和 B2。这将使数组从 AB1B2 变为 B2B1A。

步骤 3：当 A 和 B 的大小相等时，交换它们。

方法：使用递归

以下程序使用了上述算法。

文件名：RotateArray.java

public class RotateArray
{
// A Wrapper method over the recursive method leftRotateRecursive()
// It rotates the array elements by r.
public void leftRotate(int arr[], int r, int s)
{
leftRotateRecursive(arr, 0, r, s);
}
public void leftRotateRecursive(int input[], int j, int r, int s)
{
// the array will remain the same when size of the 
// input array is equal to the number of times the 
// the array is rotated. Also, if we do not rotate the array 
// at all we get the same array
if(r == 0 || r == s)
{
return;
}
// If the number of elements that has to be 
// rotated is exactly half of the input array size 
if(s - r == r)
{
swap(input, j, s - r + j, r);
return;
}
// If A is short in length
if(r < s - r)
{
swap(input, j, s - r + j, r);
leftRotateRecursive(input, j, r, s - r);	
}
else // B is short in length
{
swap(input, j, r, s - r);
leftRotateRecursive(input, s - r + j, 2 * r - s, r); 
}
}
// The method swaps the r elements
// beginning at the index f with r elements
// starting at the index g
public void swap(int input[], int f, int g, int r)
{
int k;
int temp;
for(k = 0; k < r; k++)
{
temp = input[f + k];
input[f + k] = input[g + k];
input[g + k] = temp;
}
}
// main method
public static void main (String[] argvs)
{
// creating an object of the class RotateArray
RotateArray obj = new RotateArray();
// input 1
int arr[] = {7, 9, 8, 0, 5, 1, 6, 4};
int s = arr.length;
int r = 2;
System.out.println("The input array: ");
for(int k = 0; k < s; k++)
{
System.out.print(arr[k] + " ");
}
System.out.println();
System.out.println("The new array after rotating " + r + " times, we get");
obj.leftRotate(arr, r, s);
for(int k = 0; k < s; k++)
{
System.out.print(arr[k] + " ");
}
System.out.println("\n");
// input 2
int arr1[] = {6, 8, 7, 9, 0, 5, 1, 3, 2, 4};
s = arr1.length;
r = 5;
System.out.println("The input array: ");
for(int k = 0; k < s; k++)
{
System.out.print(arr1[k] + " ");
}
System.out.println();
System.out.println("The new array after rotating " + r + " times, we get");
obj.leftRotate(arr1, r, s);
for(int k = 0; k < s; k++)
{
System.out.print(arr1[k] + " ");
}
}
}
<p><strong>Output:</strong></p>
<div class="codeblock3"><pre>
The input array: 
7 9 8 0 5 1 6 4 
The new array after rotating 2 times, we get
8 0 5 1 6 4 7 9 

The input array: 
6 8 7 9 0 5 1 3 2 4 
The new array after rotating 5 times, we get
5 1 3 2 4 6 8 7 9 0
</pre></div>
<h2 class="h2">Approach: Using Iteration</h2>
<p>Using loops also, one can achieve the same result. The following program shows the same.</p>
<p><strong>FileName:</strong> RotateArray1.java</p>
<div class="codeblock"><textarea name="code" class="java">
public class RotateArray1
{
// It rotates the array elements by r.
public void leftRotate(int input[], int r, int s)
{
int j, k;
// the array will remain the same when size of the 
// input array is equal to the number of times the 
// the array is rotated. Also, if we do not rotate the array 
// at all we get the same array
if(r == 0 || r == s)
{
return;
}
// If the number of elements that have to be rotated is
// greater than the array size
if(r > s)
{
r = r % s;
}
j = r;
k = s - r;
while (j != k)
{
if(j < k) // if A is of short in size
{
swap(input, r - j, r + k - j, j);
k = k - j;
}
else // If B is short in size
{
swap(input, r - j, r, k);
j = j - k;
}
}
// In the end, do the block swap A and B
swap(input , r - j, r, j);
}
// The method swaps the r elements
// beginning at the index f with r elements
// starting at the index g
public void swap(int input[], int f, int g, int r)
{
int k;
int temp;
for(k = 0; k < r; k++)
{
temp = input[f + k];
input[f + k] = input[g + k];
input[g + k] = temp;
}
}
// main method
public static void main (String[] argvs)
{
// creating an object of the class RotateArray1
RotateArray1 obj = new RotateArray1();
// input 1
int arr[] = {7, 9, 8, 0, 5, 1, 6, 4};
int s = arr.length;
int r = 2;
System.out.println("The input array: ");
for(int k = 0; k < s; k++)
{
System.out.print(arr[k] + " ");
}
System.out.println();
System.out.println("The new array after rotating " + r + " times, we get");
obj.leftRotate(arr, r, s);
for(int k = 0; k < s; k++)
{
System.out.print(arr[k] + " ");
}
System.out.println("\n");
// input 2
int arr1[] = {6, 8, 7, 9, 0, 5, 1, 3, 2, 4};
s = arr1.length;
r = 5;
System.out.println("The input array: ");
for(int k = 0; k < s; k++)
{
System.out.print(arr1[k] + " ");
}
System.out.println();
System.out.println("The new array after rotating " + r + " times, we get");
obj.leftRotate(arr1, r, s);
for(int k = 0; k < s; k++)
{
System.out.print(arr1[k] + " ");
}
}
}

输出

The input array: 
7 9 8 0 5 1 6 4 
The new array after rotating 2 times, we get
8 0 5 1 6 4 7 9 

The input array: 
6 8 7 9 0 5 1 3 2 4 
The new array after rotating 5 times, we get
5 1 3 2 4 6 8 7 9 0

下一个主题Java 中的最小分组大小差（两个元素）

Java 中的块交换算法或数组旋转

数组旋转示例

块交换算法

方法：使用递归

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 中的块交换算法或数组旋转

数组旋转示例

块交换算法

方法：使用递归

相关帖子

查找数组中每个元素出现频率的 Java 程序

Reserve String without reverse() function

Java 中的交错字符串问题

Java 中将零移到末尾

Java 数组所有元素求和的程序

How to Print ASCII Value in Java

Java 打印螺旋图案的程序

nth Prime Number Java

Java 查找字符串中出现次数最多和最少的字符的程序

查找数组中第二小数字的 Java 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器