A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.
The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.
You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.
For example, you are given integer X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.
Write a function:
def solution(X, A)
that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
If the frog is never able to jump to the other side of the river, the function should return −1.
For example, given X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.
Write an efficient algorithm for the following assumptions:
- N and X are integers within the range [1..100,000];
- each element of array A is an integer within the range [1..X].
有一只小青蛙想去河的对面。小青蛙初始在河的一边，位置为（position 0），想去到河的对面位置为（position X）。河边有一颗树在掉落树叶，小青蛙无法直接过河，只能在position0-position X都有连续树叶的时候才能过河。假设河的距离是X，从河的一边到另一边是1-X, 假设1-X是连续的。设数组A存储掉落的树叶的位置集合，数组的索引是K是掉落时的时间 单位是秒，假设当最后一个位置落上树叶时，青蛙可以过河。目标是找到一种简单有效的方法去到达河对岸。
例如：当河道距离X为5的时候，落叶集合为A = [1,3,1,4,2,3,5,4], K为A的索引即树叶下落的时间
| K(树叶下落时间) | X 河道位置 | 有树叶的位置 | 是否可以过河 |
| 0 | A[0]=1 | 1 | 否 |
| 1 | A[1]=2 | 1，2 | 否 |
| 2 | A[2]=1 | 1，2 | 否 |
| 3 | A[3]=4 | 1，2，4 | 否 |
| 4 | A[4]=2 | 1，2，4 | 否 |
| 5 | A[5]=3 | 1，2，3，4 | 否 |
| 6 | A[6]=5 | 1，2，3，4，5 | 是 |
由上表可知，当第6秒的时候，河道所有位置都有树叶，小青蛙可以过河
基于以上分析，我们可以给出算法结构
1. 定义一个数组长度为L，存储已经落下的树叶的时间
2. 遍历树叶集合，将位置上最早落下树叶的时间存储到L
3. L中最大的元素即是最后一片树叶落下的时间
下面看一下代码
def solution1(X, A):
earliestTime = -1
L = [-1]*X
for i in range(len(A)):
if L[A[i] - 1] == -1:
L[A[i] - 1] = i
minv = min(L)
maxv = max(L)
if minv == -1:
earliestTime = -1
else:
earliestTime = maxv
return earliestTime
当然，算法肯定不止这一种，如果有更简便高效的算法，希望可以互相交流学习