`

Array Puzzle

阅读更多
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之前又被替换了一次,就需要继续用上面的方法查找。
0
0
分享到:
评论
5 楼 andyjojo 2010-11-25  

证明是O(n)的还真难
4 楼 andyjojo 2010-11-25  
使用环运算
public static void change3(int[] loc){
		int n2 = loc.length-1, n = loc.length>>1 ;
		int change = 2;
		int t,s,at;
		for(int i=1;;i+=2){
			if(ischanged(n2,i))continue;
			at = loc[i];
			s = i;
			t=getpre(n,i);
			while(t!=i){
				loc[s] = loc[t];
				change++;
				s = t;
				t=getpre(n,s);
			}
			loc[s] = at;
			change++;
			if(change==loc.length)return;
		}
	}
	
	public static int getpre(int n, int k){
		if((k&1)==1)
			return n+(k>>1);
		return k>>1;
	}
	
	public static boolean ischanged(int n2, int k){
		int t = (2*k)%n2;
		while(t>k)t = (2*t)%n2;
		return t<k;
	}
3 楼 andyjojo 2010-11-24  
那么L(j)为不断将L'作用到j上,直到L(j)>=j
L'(j)比j小可能在于j的二进制末尾0太多了,而n到2n-1中二进制末尾0很多的应该是O(log n)
这些数最多移动O(log n)次,所以存在一些运算不超过O(log n log n),但是这个比O(n)小,所以不影响总复杂的。
呵呵,还没有想到严格证明
2 楼 andyjojo 2010-11-24  
再来:
考虑x[0,1,2,...,2n-1],即k=j-1
如果k是奇数(k二进制最后一位为1),L'(k) = n+(k-1)/2
如果k是偶数(k二进制最后一位为0),L'(k) = L'(k/2)
即把k的最后一位0删除,继续再计算,同理如果k/2末尾是0,继续计算k/2/2,直到末尾是1
则L'(k) = n+(k/(k-k&(k-1))-1)/2(不一定最优)
设k的二进制为ab...c100...0
k-1 = ab...c011...1
k&(k-1) = ab...c000...0
k-k&(k-1) = 100...0
k/(k-k&(k-1)) = abc1
即把k末尾的所有0移除了。
至于L'(k)的执行次数,应该是O(1)的,这一步还需要证明
1 楼 andyjojo 2010-11-24  
添加说明:
a1不用换
a2和b1换(b1对应整个数组的第n个数)
a3的位置在结果中应该是a2,那就要找a2在什么地方,a2在第二次是和b1换了,也就是说现在a2在b1的位置,所以a3和b1还即可
假设已换完j-1位,及1到j-1位置上以和结果一致,需要换j位
现假设处理j位时,其结果中需要的那个元素此时的位置是L(j)
如果j是偶数,那么结果应该是b(j/2),即和b(j/2)交换即可(对应整个数组的第n+j/2个数,即L(j)=n+j/2)
如果j是奇数,那么结果应该是a((j+1)/2),那就要找此时a((j+1)/2)所在的位置,肯定不在数组的(j+1)/2,因为在处理(j+1)/2时,已被替换到别的位置,而这个位置就是L((j+1)/2)
这样就变成计算L((j+1)/2),同理,如果(j+1)/2是偶数,L((j+1)/2)=n+((j+1)/2)/2,如果是奇数,L((j+1)/2)=L((((j+1)/2)+1)/2)
即 while(j不是偶数) j = (j+1)/2
j是偶数了并且n+j/2在该位置之后,那么拿该位置的元素与n+j/2调换即可。
如果n+j/2在该位置之前,那就还要重复上面的过程。
不知道说明白了没有,呵呵

相关推荐

    puzzle c.pdf

    本文档“puzzle c.pdf”主要聚焦于C语言编程中的各种问题与谜题,旨在帮助读者理解并解决C编程过程中遇到的各种难题。文档作者Gowri Kumar分享了一系列有趣的C编程题目,这些问题既包括常见的类型错误,也涵盖了一些...

    maze-puzzle-using-two-dimensional-array:简单的迷宫拼图

    本项目名为"maze-puzzle-using-two-dimensional-array",显然它使用了二维数组来表示迷宫,这是一种简单而有效的数据结构。下面我们将深入探讨这个主题。 在Java编程中,二维数组常用于模拟现实世界中的网格系统,...

    wordPuzzle

    《JavaScript实现WordPuzzle游戏详解》 在编程领域,JavaScript是一种广泛应用的脚本语言,尤其在Web开发中占据着核心地位。"wordPuzzle"是一个基于JavaScript实现的文字谜题游戏,旨在通过编程技术将文字游戏的...

    Word-Puzzle

    例如,我们可以使用`String.contains`方法检查用户输入的单词是否在谜题单词列表中,`String.lowercased()`将输入转化为小写以忽略大小写差异,以及`Array(String)`将字符串分割成单词数组进行比较。 此外,为了...

    c#实现的拼图游戏 拼图

    Array.Copy(puzzle, temp, puzzle.Length); int[] swapRow = new int[temp.GetLength(1)]; Array.Copy(temp, i * temp.GetLength(1), swapRow, 0, temp.GetLength(1)); Array.Copy(temp, swapIndex * temp....

    numpy对图片简单处理

    numpy_array = np.array(img) ``` 3. **查看图像形状**: 数组的形状可以告诉我们图像的维度和大小。例如,(width, height) 对于灰度图像,(width, height, 3) 对于RGB图像。 ```python print(numpy_array.shape) `...

    8PuzzleSolver:使用堆(优先级队列)和A *搜索算法的8难题求解器

    完整的作业规范可以在以下位置找到: : 8-puzzle是一款经典游戏,其中将图块1-8放置在3 x 3网格上,并留出一个空白空间(如果将图块1-(N ^ 2-1)放置在N x N网格上,则游戏会变大)。 目的是通过将图块滑入空白...

    flash 拼图游戏

    在拼图游戏的实现过程中,还会涉及到一些其他关键概念,如时间轴控制(Timeline Control)、对象实例化(Object Instantiation)以及数组和对象字典(Array和Object Dictionary)的使用,这些都对于管理拼图块的状态...

    树tree、动态数组dyArray、hashMap、拼图算法.zip

    本压缩包文件涵盖了四个关键概念:树(Tree)、动态数组(Dynamic Array)、哈希映射(HashMap)以及拼图算法(Puzzle Algorithm)。接下来,我们将详细探讨这些知识点。 1. **树(Tree)**: 树是一种非线性的...

    前端游戏小项目html+css+js.zip

    此外,函数(`function`)和条件语句(`if...else`)用于控制游戏流程,数组(`array`)和循环(`for`、`while`)常用于处理游戏数据。对于初学者来说,理解变量、数据类型、作用域以及异步编程(如回调函数、...

    Sudoku-Solver:基于 PHP 的数独解谜

    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...

    interview question

    if array[i] + array[j] == target print(array[i], array[j]) ``` #### 方法二:哈希表 利用哈希表可以将时间复杂度降低到O(n)。具体做法是遍历数组,对于每个元素,计算目标值与该元素的差值,并检查差值是否...

    barbara:用于花车,图像,图形和文本的声音化库

    Anne是一个用于浮点图,图像,图形和文本的声音化库。 她目前仅对文本,浮点数的数组和矩阵进行操作。...puzzle_times = np.array([12.5, 12.92, 32.08, 73.4, 25.89, 36.81, 295.22, 16.37, 225.95]) soni

    lrucacheleetcode-leetcode:leetcode

    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 ...

    拼图游戏 c++

    C++中的`std::vector`或`std::array`可以用来创建这样的数据结构。 2. **面向对象编程**:C++的面向对象特性可以帮助我们将游戏逻辑分解为不同的类,如`Puzzle`(拼图类)、`Tile`(拼图块类)等。每个类都有其特定...

    C#做的拼图小游戏

    在C#中,可以使用`Array.Equals`方法进行快速比较。 最后,对于初学者来说,理解并实现这个游戏可以帮助他们掌握C#的基础语法、面向对象编程的概念以及如何使用图形用户界面进行交互。通过这个项目,你可以学习到...

    JavaScript 圣经第5版-Javascript编程宝典--黄金版 .rar

    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. ...

    Practical C++ Programming C++编程实践

    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 ...

Global site tag (gtag.js) - Google Analytics