当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-谷歌面试题-给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数

发表于: 2012-03-31   作者:bylijinnan   来源:转载   浏览:
摘要: public class SearchInShiftedArray { /** * 题目:给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数。 * 请在这个特殊数组中找出给定的整数。 * 解答: * 其实就是“旋转数组”。旋转数组的最小元素见http://bylijinnan.iteye.com/bl

public class SearchInShiftedArray {

	/**
	 * 题目:给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数。
	 * 请在这个特殊数组中找出给定的整数。
	 * 解答:
	 * 其实就是“旋转数组”。旋转数组的最小元素见http://bylijinnan.iteye.com/blog/1431531
	 * 采用类似二分查找的策略。首先比较a[0]和a[N/2],如果a[0] < a[N/2],则说明a[0,1,...,N/2]为递增子序列,否则另一部分是递增子序列。
	 * 然后判断要找的整数是否在递增子序列范围内。如果在,则使用普通的二分查找方法继续查找;如果不在,则重复上面的查找过程,直到找到或者失败为止。
	 * 
	 */
	public static void main(String[] args) {
		int[][] a={
				{1,2,3,4,5},
				{2,3,4,5,1},
				{3,4,5,1,2},
				{4,5,1,2,3},
				{5,6,1,2,3,4},
				};
		for(int[] each:a){
			int pos=find(each,0,each.length-1,4);
			System.out.println(pos);
		}
	}

	public static int find(int[] data,int low,int high,int target){
		if(data==null||data.length==0){
			return -1;
		}
		int len=data.length;
		if(!(low>=0&&low<len&&high>=0&&high<len)){//0<=(low,high)<=len-1
			return -1;
		}
		int mid=0;
		while(low<=high){
			if(data[low]<=data[high]){//if 'data' is already increasing 
				return binarySearch(data,low,high,target);
			}
			mid=(low&high)+(low^high)/2;
			if(data[low]<=data[mid]){//if the first part is increasing
				if(target>=data[low]&&target<=data[mid]){
					return binarySearch(data,low,mid,target);
				}else{
					return find(data,mid,high,target);
				}
			}
			if(data[mid]<=data[high]){//if the second part is increasing
				if(target>=data[mid]&&target<=data[high]){
					return binarySearch(data,mid,high,target);
				}else{
					return find(data,low,mid,target);
				}
			}
		}
		return -1;
		
	}
	
	public static int binarySearch(int[] data,int low,int high,int target){
		if(data==null||data.length==0){
			return -1;
		}
		int mid=0;
		while(low<=high){
			mid=(low&high)+(low^high)/2;
			if(data[mid]==target){
				return mid;
			}else if(data[mid]<target){
				low=mid+1;
			}else{
				high=mid-1;
			}
		}
		return mid;
	}
}

java-谷歌面试题-给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1.题目。 题目:返回一个整数数组中最大子数组的和。 要求: 输入一个整形数组,数组里有正数也有负
1.题目。 题目:返回一个整数数组中最大子数组的和。 要求: 输入一个整形数组,数组里有正数也有负
1.题目 输入一个二维整形数组,数组里有正数也有负数。 求所有子数组的和的最大值。 2.设计思想 在
1.题目。 题目:返回一个二维整数数组中最大子数组的和。 要求: 输入一个二维整形数组,数组里有正
题目:返回一个二维整数数组中最大子数组的和。 要求: 1 输入一个二维整形数组,数组里有正数也有负
一、题目及要求: 题目:返回一个整数数组中最大子数组的和 要求(新加):①输入一个二维整形数组
1.题目。 题目:返回一个二维整数数组中最大子数组的和。 要求: 输入一个二维整形数组,数组里有正
1.题目 输入一个二维整形数组,数组里有正数也有负数。 求所有子数组的和的最大值。 2.设计思想 在
一、题目及要求: 题目:返回一个整数数组中最大子数组的和 要求(新加):①输入一个二维整形数组
题目:返回一个二维整数数组中最大子数组的和。 要求: 1 输入一个二维整形数组,数组里有正数也有负
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号