change array={a1,a2,...,an,b1,b2,...,bn} to {a1,b1,a2,b2,...,an,bn} with O(n) time and O(1) space.
int j, temp = 0, n = array.length / 2;
for (int i = 1; i < array.length - 1; i++) {
temp = 0;
j = i ;
j = n + (j/((j^(j-1))+1));
while (j < i) {
j = n + (j/((j^(j-1))+1));
}
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
package com.onezero;
/**
* change array {a1,a2,...an,b1,b2,...bn}
* to {a1,b1,a2,b2,...,an,bn}
* using O(n) time and O(1) space
*
* @author andyjojo
*
*/
public class ArrayPuzzle1 {
int [] array;
public ArrayPuzzle1(int[] arr){
array = arr;
}
/**
* from 1 to array.length - 1
* calculate result array i-th location
*
*/
public void change1() {
int j, temp = 0, n = array.length / 2;
for (int i = 1; i < array.length - 1; i++) {
temp = 0;
j = i + 1;
while (j % 2 == 1)
j = (j + 1) / 2;
j = n + j / 2 - 1;
while (j < i) {
j++;
while (j % 2 == 1)
j = (j + 1) / 2;
j = n + j / 2 - 1;
}
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
/**
* The magic calculation of {@link#change1()}
*
*/
public void change2(){
int j, temp = 0, n = array.length / 2;
for (int i = 1; i < array.length - 1; i++) {
temp = 0;
j = i ;
j = n + (j/((j^(j-1))+1));
while (j < i) {
j = n + (j/((j^(j-1))+1));
}
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
/**
* find in http://discuss.techinterview.org/default.asp?interview.11.482833.2
* it not work, need to check what it work for.
*/
/*public void changeother(){
int n = array.length/2;
for(int i=0;i<n;++i)
{
array[i]^=array[n+i]^=array[i]^=array[n+i];
}
}*/
/**
* print the array
*/
public void print() {
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
/**
* compares with a array
* @param b array b
* @return true when array b is the same with array, false otherwise
*/
public boolean compare(int[] b) {
if(array.length!=b.length) return false;
for (int i = 0; i < array.length; i++) {
if (array[i] != b[i])
return false;
}
return true;
}
/**
* construct a 2n element array {array[i]=i}
* aka. ai=i, bi=n+i
* @param n the half number of array length
* @return a 2n element array {ai=i}
*/
public static int[] constructOrignal(int n) {
int[] array = new int[n * 2];
for (int i = 0; i < 2*n; i++) {
array[i] = i;
}
return array;
}
/**
* construct the result of this puzzle of array {array[i]=i}
* @param n the half number of array length
* @return the result of this puzzle of array {array[i]=i}
*/
public static int[] constructResult(int n) {
int[] array = new int[n * 2];
for (int i = 0; i < n; i++) {
array[2 * i] = i;
array[2 * i + 1] = n + i;
}
return array;
}
/**
* @param args
*/
public static void main(String[] args) {
ArrayPuzzle1 ap;
for (int i = 1; i < 9999; i++) {
ap = new ArrayPuzzle1(constructOrignal(i));
ap.change2();//the same with ap.change1()
if (!ap.compare(constructResult(i)))
System.out.println("Fail on " + i);
}
}
}
说明(一下内容反选可见,你可以看完代码再看。希望收到你的意见,谢谢):
1 和 2n 的位置不用换
j 从 2 到 2n-1
如果j是偶数,只要直接与n+j/2交换即可
如果j是奇数,那么就要放置a[(j+1)/2]即可,那么问题就是要找到a[(j+1)/2]当前的位置
因为(j+1)/2<j,所以在处理(j+1)/2时,a[(j+1)/2] 已经不在(j+1)/2了,替换到(j+1)/2位置上元素没有替换之前的位置,所以在考虑(j+1)/2即可。
比如位置5,应该是a3, 而对于3,应该是a2, 同样对于2,应该是b1, 即n+1位置,所以a3此时应该在n+1的位置。
如果按照上面的位置找到j需要替换的元素位置小于j,说明该元素在j之前又被替换了一次,就需要继续用上面的方法查找。
分享到:
相关推荐
迷宫拼图二维数组简单的迷宫拼图运行程序,它将显示迷宫是使用rlud键移动的起点(输入eack键后,按Enter键)
完整的作业规范可以在以下位置找到: : 8-puzzle是一款经典游戏,其中将图块1-8放置在3 x 3网格上,并留出一个空白空间(如果将图块1-(N ^ 2-1)放置在N x N网格上,则游戏会变大)。 目的是通过将图块滑入空白...
array ( 0 , 6 , 0 , 0 , 0 , 0 , 0 , 3 , 0 ), array ( 0 , 0 , 0 , 5 , 0 , 0 , 0 , 0 , 4 ), array ( 4 , 1 , 0 , 0 , 0 , 9 , 0 , 2 , 0 ), array ( 0 , 0 , 4 , 0 , 0 , 0 , 0 , 0 , 0 ), array ( 0 , 3...
Anne是一个用于浮点图,图像,图形和文本的声音化库。 她目前仅对文本,浮点数的数组和矩阵进行操作。...puzzle_times = np.array([12.5, 12.92, 32.08, 73.4, 25.89, 36.81, 295.22, 16.37, 225.95]) soni
Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array ...
fun, puzzle together with attractive interface design and appetizing fruit vegetables picture elements, makes this lianliankan games become the modern city spending tedious, relaxed and good help....
Chapter 56: Application: Cross-Browser DHTML Map Puzzle. Chapter 57: Application: Transforming XML Data Islands. Part VI: Appendixes. Appendix A: JavaScript and Browser Object Quick Reference. ...
File Input/Output C++ File I/O Conversion Routines Binary and ASCII Files The End-of-Line Puzzle Binary I/O Buffering Problems Unbuffered I/O Designing File Formats C-Style I/O Routines C-Style ...
pygame.PixelArray Objects .............................................................................................. 23 The pygame.display.update() Function ..........................................
该存储库包含一些算法和数据结构,这些算法和数据结构主要用于踢球和学习。 希望可以帮助需要帮助的人! 随意分叉,复制,提出更正或提出问题。 快乐的编码:) gradle wrapper --gradle-version 2.0