数组:如何求指定数字在数组中第一次出现的位置

  • Post author:
  • Post category:其他


问题描述:

给定数组 a = { 3,4,5,6,5,6,7,8,9,8},

这个数组相邻元素之差都为1

, 给定数字9, 它在数组中第一次出现的位置下标为8

实现思路:

方法一:“蛮力”法,顺序遍历一遍数组中每一个元素,与9比较,时间复杂度为O(n)

方法二:

跳跃搜索法

。首先用数组中第一个元素3与9进行比较,差值为6,由于相邻两个元素的差值为1,因此9在数组中出现最早的位置必定为:1+6 = 7 个位置(下标为6)。

如果数组是递增的,那么数组第7个元素的值才为9,如果不是递增的,那么9出现的位置肯定在第7个元素后面。

实现代码:

/**
	 * 跳跃搜索法
	 * @param a
	 * @param val
	 * @return
	 */
	private int findIndex(int[] a, int val) {
		if(a == null)
			return -1;
		int len = a.length;
		if(len < 1)
			return -1;
		int index = 0;
		while(index < len){
			if(a[index] == val)
				return index;
			else
				index += Math.abs(val-a[index]);
		}
		return -1;
	}

测试代码:

@Test
	public void main(){
		int a[] = {3,4,5,6,5,6,7,8,9,8};
		int index = findIndex(a,9);
		System.out.println(index);
	}

实现效果:



版权声明:本文为weixin_38108266原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。