查找丢失的数字

有一道题是在1~n中的数组中寻找丢失的那个数字。
比较好的方式就是异或,因为全+的话,有溢出的风险。所以异或是不错的。

    function findmissingnumber(arr,n){
	for(var i = 0,number;i<n;i++){
		number^=((i+1)^arr[i]);
	}
	return number;
    }

leetcode上有一道变了一点的题,find the missing positive ,还需要点时间弄懂解决,这篇文章待续······

在网上搜了下,看到一篇文章:http://www.cnblogs.com/AnnieKim/archive/2013/04/21/3034631.html
有些参考,不过还没有最终理解,先改为JS的看看:

                function swap(arr,i,k){
			var temp;
			temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}
		function findmissingpositive2(arr,n){
			var i = 0;
			while(i < n){
				if(arr[i] != (i+1) && arr[i] >=1 && arr[i] <= n && arr[arr[i]-1] != arr[i]){
					swap(arr,i,arr[i]-1);
				}else{
					i++;
				}
			}
			for (i = 0; i < n; ++i){
				if(arr[i]!=(i+1)){
					return i+1;
				}
			}
			return n+1;
		}

貌似是使用了位图法的思想。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据