d****o 发帖数: 1055 | 1 这道题谁能解出来?(注意,这道题题意请理解清楚)
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
and [-3,-4,1,2,6,7] return 3
Your algorithm should run in O(n) time and uses constant space. |
h****e 发帖数: 928 | 2 这道题在LeetCode上有的,叫做First Missing Positive
http://www.leetcode.com/onlinejudge
没做出来,但是网上可以找到解法的。 |
b***d 发帖数: 87 | 3 public static int findFirstMissPositive(int[] a)
{
Arrays.sort(a);
int i=0;
while(i
{
if(a[i]<=0)
{
i++;
}
else
{
if(i+1
{
i++;
}
else
{
break;
}
}
}
return a[i]+1;
}
欢迎拍砖! |
h****e 发帖数: 928 | 4 第一行做了排序,复杂度就变成O(nlogn)了。
【在 b***d 的大作中提到】 : public static int findFirstMissPositive(int[] a) : { : Arrays.sort(a); : int i=0; : while(i: { : if(a[i]<=0) : { : i++; : }
|
c****p 发帖数: 6474 | 5 换换换换换
【在 h****e 的大作中提到】 : 这道题在LeetCode上有的,叫做First Missing Positive : http://www.leetcode.com/onlinejudge : 没做出来,但是网上可以找到解法的。
|
s*******i 发帖数: 7 | 6 1.只考虑数组里的元素都>1的情况,因为其它任何数组可以在O(N)的复杂度内变成>1的
情况(用0做pivot把数组划开,<=0的部分不考虑)。
2.假设现在有数组A[1..N],且A[i]>1,那么有个“不”符合题目要求的线性算法:
设bool B[1..N],B[i]表示i在A[1..N]里出现过了,显然B数组线性时间就能算完。
但是它不符合题目中说的常数的额外空间。
3.我们想一下如何能把A和B只用A就表示了?
可以这样:因为A[i]>1,当我们在A[i]里看到一个元素j时,如果j>N就不用管,否则就
把A[j]里的数字变成负数。这样就可以用负号来代替那个B数组。
整个时间复杂度还是线性的,并且额外的空间是常数的。 |
l*********8 发帖数: 4642 | 7 int firstMissingPositive(int A[], int n) {
for (int i=0; i
while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
swap(A[i], A[A[i]-1]);
for (int i=0; i
if(A[i] != i+1)
return i+1;
return n+1;
} |
p*****2 发帖数: 21240 | |
q***y 发帖数: 236 | |
o*******y 发帖数: 115 | 10 写了个O(n)的
int firstPositive(int[] A)
{
int i = 0;
while(i < A.length)
{
if(A[i] < A.length && A[i] > 0 && A[A[i]] != A[i])
//把正数A[i]放到第i个位置
swap(A[i], A[A[i]]);
else
i++;
}
for(i = 1; i < A.length; i++)
{
if(A[i] != i) // 第i个位置上不是正数i则返回i
return i;
}
if(A[0] == A.length) // A[0]恰好是A.length则返回下一个正整数A.length+1
return A.length+1;
else // A[0] <=0 或者 > A.length, 则返回A.length
return A.length;
} |
|
|
r****k 发帖数: 21 | 11 重新构造数组,如果当前下标的value>0 && <=数组长度,则设置a[value-1] = value
例如原数组为: -3, -4, 1, 2, 6, 7
新数组为: 1, 2, 1, 2, 6, 6
然后循环数组,找到值不等于下标+1的i(a[i]!=i+1),返回i+1
int findFirstMissingPositive(int a[], int length)
{
int temp = 0;
int i = 0;
int value;
while (i < length)
{
if (temp > 0)
{
value = temp;
}
else
{
value = a[i];
i++;
}
if (value > 0 && value <= length)
{
if (a[value-1] == value)
{
temp = 0;
}
else
{
temp = a[value-1];
a[value-1] = value;
}
}
else
{
temp = 0;
}
}
for (i = 0; i < length; i++)
{
if (a[i] != i+1)
break;
}
return i+1;
} |
l****c 发帖数: 782 | 12 我也mark一下吧,
不知道不用sort怎么找first missing positive,
用了sort就不O n 了 |
p*****2 发帖数: 21240 | 13
我发现我很懒的看代码。能说说思路吗?
【在 l*********8 的大作中提到】 : int firstMissingPositive(int A[], int n) { : for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1]) : swap(A[i], A[A[i]-1]); : for (int i=0; i: if(A[i] != i+1) : return i+1; : return n+1; : }
|
p*****2 发帖数: 21240 | 14
chenpp的思路应该是对的。
【在 l****c 的大作中提到】 : 我也mark一下吧, : 不知道不用sort怎么找first missing positive, : 用了sort就不O n 了
|
w****x 发帖数: 2483 | 15
二爷, 你Facebook面的到底怎么样了??
【在 p*****2 的大作中提到】 : : chenpp的思路应该是对的。
|
l*********8 发帖数: 4642 | 16 我的思路基本和onlysunny一样。
【在 p*****2 的大作中提到】 : : chenpp的思路应该是对的。
|
h*****f 发帖数: 248 | 17 不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive
integer= 4?
or the absolute value of the number must be between 0 and last index+1? |
h*******s 发帖数: 8454 | 18 1
【在 h*****f 的大作中提到】 : 不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive : integer= 4? : or the absolute value of the number must be between 0 and last index+1?
|
p*****2 发帖数: 21240 | 19 我写了一个
public int firstMissingPositive(int[] A)
{
int n = A.length;
int i = 0;
int j = n - 1;
while (i <= j)
{
while (i < n && A[i] >= 1 && A[i] <= n)
i++;
while (j >= 0 && (A[j] <= 0 || A[j] > n))
j--;
if (i < j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
i++;
j--;
}
}
for (i = 0; i <= j; i++)
{
int a = Math.abs(A[i]);
if (A[a - 1] > 0)
A[a - 1] = -A[a - 1];
}
for (i = 0; i <= j; i++)
if (A[i] > 0)
break;
return i + 1;
} |
p*****2 发帖数: 21240 | 20
不行备,看你的了。
【在 w****x 的大作中提到】 : : 二爷, 你Facebook面的到底怎么样了??
|
|
|
j*******h 发帖数: 20 | 21 public class FirstMissingPositive {
int min;//Integer.MAX_VALUE;
int max;//Integer.MIN_VALUE;
private void checkMinMax(){
if( max > 0 && min > 0 ){
if( max < min ){
int temp = min;
min = max;
max = temp;
}
if( max - min > 1 )
max = -1;
}
}
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
min = -1;
max = -1;
boolean hasOne = false;
if (A.length <= 0 )
return 1;
if(A.length == 1 && A[0] != 1)
return 1;
if(A.length == 1 && A[0] == 1)
return 2;
for (int i = 0; i < A.length; i++) {
if (A[i] <= 0)
continue;
if( A[i] == 1 )
hasOne = true;
// initialize
if( min == -1 ){
min = A[i];
checkMinMax();
continue;
}
if( max == -1 ){
max = A[i];
checkMinMax();
continue;
}
if (A[i] < min) {
max = min;
min = A[i];
checkMinMax();
}else if( A[i] > max ){
min = max;
max = A[i];
checkMinMax();
}
}
if( !hasOne )
return 1;
return max == -1 ? (min + 1) : (max + 1);
}
public static void main(String[] Args) {
int[] a = { -10,-3,-100,-1000,-239,1 };
int[] b = { 3,2 };
int[] c = { 2,2 };
int[] d = { 4, 1, 2, 3 };
FirstMissingPositive temp = new FirstMissingPositive();
System.out.println(Arrays.toString(a) + " --- "
+ temp.firstMissingPositive(a));
System.out.println(Arrays.toString(b) + " --- "
+ temp.firstMissingPositive(b));
System.out.println(Arrays.toString(c) + " --- "
+ temp.firstMissingPositive(c));
System.out.println(Arrays.toString(d) + " --- "
+ temp.firstMissingPositive(d));
}
} |
H*******g 发帖数: 6997 | 22 呵呵,我习惯性的用QUERY来解决,供你参考
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
y***d 发帖数: 2330 | 23 find the max, min, sum and the ought-to-be sum if there were nothing missing
pretty dummy solution though
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
c*******a 发帖数: 35 | 24 如果这个数组只miss一个元素,那这是最有效的解法了。
但如果miss多个元素,就不行了。
missing
【在 y***d 的大作中提到】 : find the max, min, sum and the ought-to-be sum if there were nothing missing : pretty dummy solution though
|
z********i 发帖数: 568 | 25 /* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i
/* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i];
while(val>0 && val<=n && val!=A[val-1]){
index=val-1;
val=A[index];
A[index]=index+1;
}
}
/* find the first missing postive integer A[i] where A[i]!=i+1 */
x=0; //return 0 if no missing postive integer from 1 to n
outFile<<"Array after rearraged"<
for(i=0;i
outFile<
if(A[i]!=i+1){
x=i+1;
break;
}
}
outFile<
return x;
}
Complexity is O(n) in time and O(1) in space.
The main difficulty on complexity is the while loop inside the for loop for
reordering. However, since each element in the range 1..n is only reordered
only once and each other element is not reordered, so the total complexity
is still O(n). |
z********i 发帖数: 568 | 26 发现跟longway解法一样。longway解法更紧凑。
【在 z********i 的大作中提到】 : /* find the first missing postivie integer in array A with n elements : return x if one postive integer in [1..n] is missing; : return 0 otherwise; : */ : int findFirstMissingPositiveInteger(int A[], int n){ : int x,i,val,index; : /* rearrange the input array A such that : B[i]=i+1 if i+1 exist in array A, or : B[i]=A[i] if i+1 does not exist in array A : where B is the array rearraged from A.
|
m*****k 发帖数: 731 | 27 try
new int[] {40,50,40, 10,20,30}
【在 p*****2 的大作中提到】 : 我写了一个 : public int firstMissingPositive(int[] A) : { : int n = A.length; : int i = 0; : int j = n - 1; : while (i <= j) : { : while (i < n && A[i] >= 1 && A[i] <= n) : i++;
|
m*****k 发帖数: 731 | 28 so won't work for [10,20,30] ?
【在 l*********8 的大作中提到】 : int firstMissingPositive(int A[], int n) { : for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1]) : swap(A[i], A[A[i]-1]); : for (int i=0; i: if(A[i] != i+1) : return i+1; : return n+1; : }
|
l*********8 发帖数: 4642 | 29 it should return 1.
【在 m*****k 的大作中提到】 : so won't work for [10,20,30] ?
|
d*****i 发帖数: 122 | 30
【在 l*********8 的大作中提到】 : it should return 1.
|
|
|
l*********8 发帖数: 4642 | 31 我经常见到空回复。 不知道是什么意思?
【在 d*****i 的大作中提到】 :
|
C*******n 发帖数: 48 | |
s*********5 发帖数: 514 | 33 int FindFirstMissingPositiveInteger(int a[], int size)
{
int index = 0;
while (index < size)
{
while (a[index] != index && a[index] < size
&& a[index] >0)
{
int tmp = a[a[index]];
a[a[index]] = a[index];
a[index] = tmp;
}
++index;
}
index = 1;
while (index < size)
{
if (a[index] != index)
return index;
++index;
}
return index;
};
int main(int argc, char* argv[])
{
int fff1[] = {1,2,0};
int fff2[] = {3, 4, -1, 1};
int fff3[] = {-3, -4, 1, 2, 6, 7};
int fff4[] = { -10,-3,-100,-1000,-239,1};
int fff5[] = {40,50,40, 10,20,30};
cout << " fff1: " << FindFirstMissingPositiveInteger(fff1, sizeof(fff1)/
sizeof(int)) << endl;
cout << " fff2: " << FindFirstMissingPositiveInteger(fff2, sizeof(fff2)/
sizeof(int)) << endl;
cout << " fff3: " << FindFirstMissingPositiveInteger(fff3, sizeof(fff3)/
sizeof(int)) << endl;
cout << " fff4: " << FindFirstMissingPositiveInteger(fff4, sizeof(fff4)/
sizeof(int)) << endl;
cout << " fff5: " << FindFirstMissingPositiveInteger(fff5, sizeof(fff5)/
sizeof(int)) << endl;
return 0;
}
Result:
fff1: 3
fff2: 2
fff3: 3
fff4: 2
fff5: 1 |
b**a 发帖数: 1118 | 34 Can we assume that there is no duplicated elements?
that is, there is no [-3,-4,1,2,6,6,7,7]
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
g***m 发帖数: 85 | 35 数组full的空间可以无穷大...
【在 H*******g 的大作中提到】 : 呵呵,我习惯性的用QUERY来解决,供你参考
|
g***m 发帖数: 85 | 36 思路是对的,但是第一个loop扫一遍好像不够。
比如 3 4 -1 1
第一遍扫完是
-1 1 3 4
还要再来一遍,才能变成
1 -1 3 4
两遍也不够,这个扫的次数如果和n相关,就不是线性的了。
【在 l*********8 的大作中提到】 : int firstMissingPositive(int A[], int n) { : for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1]) : swap(A[i], A[A[i]-1]); : for (int i=0; i: if(A[i] != i+1) : return i+1; : return n+1; : }
|
g**x 发帖数: 373 | 37 public int firstMissingPositive(int[] A) {
if (A.length == 0) return 1;
int i=0;
while (i
if (A[i]>=0 && A[i]
if (A[i]!=i && A[i]!=A[A[i]]) {
int temp = A[A[i]];
A[A[i]] = A[i];
A[i] = temp;
continue;
}
}
i++;
}
for (i=1; i
if (i!=A[i]) return i;
}
if (A[0]==A.length) return A.length+1;
return A.length;
}
【在 g***m 的大作中提到】 : 思路是对的,但是第一个loop扫一遍好像不够。 : 比如 3 4 -1 1 : 第一遍扫完是 : -1 1 3 4 : 还要再来一遍,才能变成 : 1 -1 3 4 : 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。
|
t**i 发帖数: 314 | 38 long的答案没有问题,每次swap后,i会保持原值在while loop里再检测一遍
【在 g***m 的大作中提到】 : 思路是对的,但是第一个loop扫一遍好像不够。 : 比如 3 4 -1 1 : 第一遍扫完是 : -1 1 3 4 : 还要再来一遍,才能变成 : 1 -1 3 4 : 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。
|
g***s 发帖数: 3811 | |
b********h 发帖数: 2451 | 40 使用一个原数组一样长的数组,
找出最小正整数...
int find_least_missing(const int numbers[],const int array_length)
{
int buffer_right[array_length];
for(int i=1;i
{buffer_right[i]=0;}
int min_value=-1;
for (int i=1;i
{
if (min_value>0) {
if (min_value>numbers[i])
min_value=numbers[i];
}
else{
if (numbers[i]>0)
min_value=numbers[i];
}
}
if (min_value>1)
return 1;
buffer_right[0]=min_value;
int total_number=array_length;
int max_right=0;
bool flag_right=0;
for (int i=1;i
{
int distances;
distances=numbers[i]-min_value;
if (distances
{
if (distances>0)
{buffer_right[distances]=numbers[i];
max_right=distances;}
else
total_number--;
}
else
{total_number--;
flag_right=1;
}
}
for (int i=1;i<=max_right;i++)
{
if(buffer_right[i]==0)
return min_value+i;
}
if (flag_right)
return max_right+min_value+1;
else
return 0;
} |
|
|
d****o 发帖数: 1055 | 41 这道题谁能解出来?(注意,这道题题意请理解清楚)
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
and [-3,-4,1,2,6,7] return 3
Your algorithm should run in O(n) time and uses constant space. |
h****e 发帖数: 928 | 42 这道题在LeetCode上有的,叫做First Missing Positive
http://www.leetcode.com/onlinejudge
没做出来,但是网上可以找到解法的。 |
b***d 发帖数: 87 | 43 public static int findFirstMissPositive(int[] a)
{
Arrays.sort(a);
int i=0;
while(i
{
if(a[i]<=0)
{
i++;
}
else
{
if(i+1
{
i++;
}
else
{
break;
}
}
}
return a[i]+1;
}
欢迎拍砖! |
h****e 发帖数: 928 | 44 第一行做了排序,复杂度就变成O(nlogn)了。
【在 b***d 的大作中提到】 : public static int findFirstMissPositive(int[] a) : { : Arrays.sort(a); : int i=0; : while(i: { : if(a[i]<=0) : { : i++; : }
|
c****p 发帖数: 6474 | 45 换换换换换
【在 h****e 的大作中提到】 : 这道题在LeetCode上有的,叫做First Missing Positive : http://www.leetcode.com/onlinejudge : 没做出来,但是网上可以找到解法的。
|
s*******i 发帖数: 7 | 46 1.只考虑数组里的元素都>1的情况,因为其它任何数组可以在O(N)的复杂度内变成>1的
情况(用0做pivot把数组划开,<=0的部分不考虑)。
2.假设现在有数组A[1..N],且A[i]>1,那么有个“不”符合题目要求的线性算法:
设bool B[1..N],B[i]表示i在A[1..N]里出现过了,显然B数组线性时间就能算完。
但是它不符合题目中说的常数的额外空间。
3.我们想一下如何能把A和B只用A就表示了?
可以这样:因为A[i]>1,当我们在A[i]里看到一个元素j时,如果j>N就不用管,否则就
把A[j]里的数字变成负数。这样就可以用负号来代替那个B数组。
整个时间复杂度还是线性的,并且额外的空间是常数的。 |
l*********8 发帖数: 4642 | 47 int firstMissingPositive(int A[], int n) {
for (int i=0; i
while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
swap(A[i], A[A[i]-1]);
for (int i=0; i
if(A[i] != i+1)
return i+1;
return n+1;
} |
p*****2 发帖数: 21240 | |
q***y 发帖数: 236 | |
r****k 发帖数: 21 | 50 重新构造数组,如果当前下标的value>0 && <=数组长度,则设置a[value-1] = value
例如原数组为: -3, -4, 1, 2, 6, 7
新数组为: 1, 2, 1, 2, 6, 6
然后循环数组,找到值不等于下标+1的i(a[i]!=i+1),返回i+1
int findFirstMissingPositive(int a[], int length)
{
int temp = 0;
int i = 0;
int value;
while (i < length)
{
if (temp > 0)
{
value = temp;
}
else
{
value = a[i];
i++;
}
if (value > 0 && value <= length)
{
if (a[value-1] == value)
{
temp = 0;
}
else
{
temp = a[value-1];
a[value-1] = value;
}
}
else
{
temp = 0;
}
}
for (i = 0; i < length; i++)
{
if (a[i] != i+1)
break;
}
return i+1;
} |
|
|
l****c 发帖数: 782 | 51 我也mark一下吧,
不知道不用sort怎么找first missing positive,
用了sort就不O n 了 |
p*****2 发帖数: 21240 | 52
我发现我很懒的看代码。能说说思路吗?
【在 l*********8 的大作中提到】 : int firstMissingPositive(int A[], int n) { : for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1]) : swap(A[i], A[A[i]-1]); : for (int i=0; i: if(A[i] != i+1) : return i+1; : return n+1; : }
|
p*****2 发帖数: 21240 | 53
chenpp的思路应该是对的。
【在 l****c 的大作中提到】 : 我也mark一下吧, : 不知道不用sort怎么找first missing positive, : 用了sort就不O n 了
|
w****x 发帖数: 2483 | 54
二爷, 你Facebook面的到底怎么样了??
【在 p*****2 的大作中提到】 : : chenpp的思路应该是对的。
|
l*********8 发帖数: 4642 | 55 我的思路基本和onlysunny一样。
【在 p*****2 的大作中提到】 : : chenpp的思路应该是对的。
|
h*****f 发帖数: 248 | 56 不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive
integer= 4?
or the absolute value of the number must be between 0 and last index+1? |
h*******s 发帖数: 8454 | 57 1
【在 h*****f 的大作中提到】 : 不知道我是不是解错题,如果输入的是[11,9,7,5],那第一个missing positive : integer= 4? : or the absolute value of the number must be between 0 and last index+1?
|
p*****2 发帖数: 21240 | 58 我写了一个
public int firstMissingPositive(int[] A)
{
int n = A.length;
int i = 0;
int j = n - 1;
while (i <= j)
{
while (i < n && A[i] >= 1 && A[i] <= n)
i++;
while (j >= 0 && (A[j] <= 0 || A[j] > n))
j--;
if (i < j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
i++;
j--;
}
}
for (i = 0; i <= j; i++)
{
int a = Math.abs(A[i]);
if (A[a - 1] > 0)
A[a - 1] = -A[a - 1];
}
for (i = 0; i <= j; i++)
if (A[i] > 0)
break;
return i + 1;
} |
p*****2 发帖数: 21240 | 59
不行备,看你的了。
【在 w****x 的大作中提到】 : : 二爷, 你Facebook面的到底怎么样了??
|
j*******h 发帖数: 20 | 60 public class FirstMissingPositive {
int min;//Integer.MAX_VALUE;
int max;//Integer.MIN_VALUE;
private void checkMinMax(){
if( max > 0 && min > 0 ){
if( max < min ){
int temp = min;
min = max;
max = temp;
}
if( max - min > 1 )
max = -1;
}
}
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
min = -1;
max = -1;
boolean hasOne = false;
if (A.length <= 0 )
return 1;
if(A.length == 1 && A[0] != 1)
return 1;
if(A.length == 1 && A[0] == 1)
return 2;
for (int i = 0; i < A.length; i++) {
if (A[i] <= 0)
continue;
if( A[i] == 1 )
hasOne = true;
// initialize
if( min == -1 ){
min = A[i];
checkMinMax();
continue;
}
if( max == -1 ){
max = A[i];
checkMinMax();
continue;
}
if (A[i] < min) {
max = min;
min = A[i];
checkMinMax();
}else if( A[i] > max ){
min = max;
max = A[i];
checkMinMax();
}
}
if( !hasOne )
return 1;
return max == -1 ? (min + 1) : (max + 1);
}
public static void main(String[] Args) {
int[] a = { -10,-3,-100,-1000,-239,1 };
int[] b = { 3,2 };
int[] c = { 2,2 };
int[] d = { 4, 1, 2, 3 };
FirstMissingPositive temp = new FirstMissingPositive();
System.out.println(Arrays.toString(a) + " --- "
+ temp.firstMissingPositive(a));
System.out.println(Arrays.toString(b) + " --- "
+ temp.firstMissingPositive(b));
System.out.println(Arrays.toString(c) + " --- "
+ temp.firstMissingPositive(c));
System.out.println(Arrays.toString(d) + " --- "
+ temp.firstMissingPositive(d));
}
} |
|
|
H*******g 发帖数: 6997 | 61 呵呵,我习惯性的用QUERY来解决,供你参考
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
y***d 发帖数: 2330 | 62 find the max, min, sum and the ought-to-be sum if there were nothing missing
pretty dummy solution though
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
c*******a 发帖数: 35 | 63 如果这个数组只miss一个元素,那这是最有效的解法了。
但如果miss多个元素,就不行了。
missing
【在 y***d 的大作中提到】 : find the max, min, sum and the ought-to-be sum if there were nothing missing : pretty dummy solution though
|
z********i 发帖数: 568 | 64 /* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i
/* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i];
while(val>0 && val<=n && val!=A[val-1]){
index=val-1;
val=A[index];
A[index]=index+1;
}
}
/* find the first missing postive integer A[i] where A[i]!=i+1 */
x=0; //return 0 if no missing postive integer from 1 to n
outFile<<"Array after rearraged"<
for(i=0;i
outFile<
if(A[i]!=i+1){
x=i+1;
break;
}
}
outFile<
return x;
}
Complexity is O(n) in time and O(1) in space.
The main difficulty on complexity is the while loop inside the for loop for
reordering. However, since each element in the range 1..n is only reordered
only once and each other element is not reordered, so the total complexity
is still O(n). |
z********i 发帖数: 568 | 65 发现跟longway解法一样。longway解法更紧凑。
【在 z********i 的大作中提到】 : /* find the first missing postivie integer in array A with n elements : return x if one postive integer in [1..n] is missing; : return 0 otherwise; : */ : int findFirstMissingPositiveInteger(int A[], int n){ : int x,i,val,index; : /* rearrange the input array A such that : B[i]=i+1 if i+1 exist in array A, or : B[i]=A[i] if i+1 does not exist in array A : where B is the array rearraged from A.
|
m*****k 发帖数: 731 | 66 try
new int[] {40,50,40, 10,20,30}
【在 p*****2 的大作中提到】 : 我写了一个 : public int firstMissingPositive(int[] A) : { : int n = A.length; : int i = 0; : int j = n - 1; : while (i <= j) : { : while (i < n && A[i] >= 1 && A[i] <= n) : i++;
|
m*****k 发帖数: 731 | 67 so won't work for [10,20,30] ?
【在 l*********8 的大作中提到】 : int firstMissingPositive(int A[], int n) { : for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1]) : swap(A[i], A[A[i]-1]); : for (int i=0; i: if(A[i] != i+1) : return i+1; : return n+1; : }
|
l*********8 发帖数: 4642 | 68 it should return 1.
【在 m*****k 的大作中提到】 : so won't work for [10,20,30] ?
|
l*********8 发帖数: 4642 | 69 我经常见到空回复。 不知道是什么意思?
【在 d*****i 的大作中提到】 :
|
C*******n 发帖数: 48 | |
|
|
s*********5 发帖数: 514 | 71 int FindFirstMissingPositiveInteger(int a[], int size)
{
int index = 0;
while (index < size)
{
while (a[index] != index && a[index] < size
&& a[index] >0)
{
int tmp = a[a[index]];
a[a[index]] = a[index];
a[index] = tmp;
}
++index;
}
index = 1;
while (index < size)
{
if (a[index] != index)
return index;
++index;
}
return index;
};
int main(int argc, char* argv[])
{
int fff1[] = {1,2,0};
int fff2[] = {3, 4, -1, 1};
int fff3[] = {-3, -4, 1, 2, 6, 7};
int fff4[] = { -10,-3,-100,-1000,-239,1};
int fff5[] = {40,50,40, 10,20,30};
cout << " fff1: " << FindFirstMissingPositiveInteger(fff1, sizeof(fff1)/
sizeof(int)) << endl;
cout << " fff2: " << FindFirstMissingPositiveInteger(fff2, sizeof(fff2)/
sizeof(int)) << endl;
cout << " fff3: " << FindFirstMissingPositiveInteger(fff3, sizeof(fff3)/
sizeof(int)) << endl;
cout << " fff4: " << FindFirstMissingPositiveInteger(fff4, sizeof(fff4)/
sizeof(int)) << endl;
cout << " fff5: " << FindFirstMissingPositiveInteger(fff5, sizeof(fff5)/
sizeof(int)) << endl;
return 0;
}
Result:
fff1: 3
fff2: 2
fff3: 3
fff4: 2
fff5: 1 |
b**a 发帖数: 1118 | 72 Can we assume that there is no duplicated elements?
that is, there is no [-3,-4,1,2,6,6,7,7]
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
g***m 发帖数: 85 | 73 数组full的空间可以无穷大...
【在 H*******g 的大作中提到】 : 呵呵,我习惯性的用QUERY来解决,供你参考
|
g***m 发帖数: 85 | 74 思路是对的,但是第一个loop扫一遍好像不够。
比如 3 4 -1 1
第一遍扫完是
-1 1 3 4
还要再来一遍,才能变成
1 -1 3 4
两遍也不够,这个扫的次数如果和n相关,就不是线性的了。
【在 l*********8 的大作中提到】 : int firstMissingPositive(int A[], int n) { : for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1]) : swap(A[i], A[A[i]-1]); : for (int i=0; i: if(A[i] != i+1) : return i+1; : return n+1; : }
|
g**x 发帖数: 373 | 75 public int firstMissingPositive(int[] A) {
if (A.length == 0) return 1;
int i=0;
while (i
if (A[i]>=0 && A[i]
if (A[i]!=i && A[i]!=A[A[i]]) {
int temp = A[A[i]];
A[A[i]] = A[i];
A[i] = temp;
continue;
}
}
i++;
}
for (i=1; i
if (i!=A[i]) return i;
}
if (A[0]==A.length) return A.length+1;
return A.length;
}
【在 g***m 的大作中提到】 : 思路是对的,但是第一个loop扫一遍好像不够。 : 比如 3 4 -1 1 : 第一遍扫完是 : -1 1 3 4 : 还要再来一遍,才能变成 : 1 -1 3 4 : 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。
|
t**i 发帖数: 314 | 76 long的答案没有问题,每次swap后,i会保持原值在while loop里再检测一遍
【在 g***m 的大作中提到】 : 思路是对的,但是第一个loop扫一遍好像不够。 : 比如 3 4 -1 1 : 第一遍扫完是 : -1 1 3 4 : 还要再来一遍,才能变成 : 1 -1 3 4 : 两遍也不够,这个扫的次数如果和n相关,就不是线性的了。
|
g***s 发帖数: 3811 | |
b********h 发帖数: 2451 | 78 使用一个原数组一样长的数组,
找出最小正整数...
int find_least_missing(const int numbers[],const int array_length)
{
int buffer_right[array_length];
for(int i=1;i
{buffer_right[i]=0;}
int min_value=-1;
for (int i=1;i
{
if (min_value>0) {
if (min_value>numbers[i])
min_value=numbers[i];
}
else{
if (numbers[i]>0)
min_value=numbers[i];
}
}
if (min_value>1)
return 1;
buffer_right[0]=min_value;
int total_number=array_length;
int max_right=0;
bool flag_right=0;
for (int i=1;i
{
int distances;
distances=numbers[i]-min_value;
if (distances
{
if (distances>0)
{buffer_right[distances]=numbers[i];
max_right=distances;}
else
total_number--;
}
else
{total_number--;
flag_right=1;
}
}
for (int i=1;i<=max_right;i++)
{
if(buffer_right[i]==0)
return min_value+i;
}
if (flag_right)
return max_right+min_value+1;
else
return 0;
} |
j**7 发帖数: 143 | 79 static int findPositive(int [] input)
{
int length=input.length;
for(int i=0;i
{
if(input[i]!=i+1 && input[i]<=length &&input[i]>=1)
{
int temp=input[i];
input[i]=input[input[i]-1];
input[temp-1]=temp;
}
}
for(int i=0;i
{
if(input[i]!=i+1)
return i+1;
}
return length+1;
} |
A***o 发帖数: 358 | 80 O(n) time, O(n) space
int find(vector & input){
vector check;
check.resize(input.size(),0);
for(int i=0;i
if(input[i]>0 && input[i]<=input.size())
check[ input[i]-1 ]=input[i];
}
for(int i=0;i
if(check[i]==0)
return i+1;
}
return check.size()+1;
} |
|
|
b*******e 发帖数: 217 | 81 build a min-heap in o(n).
query the min element.
query the two child ot he min element.
if the three elements not consecutive. find the missing interger already.
Otherwiese, go to the smaller child until the missing integer is found. o(
logn)
complexity = o(n) + o(logn)
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
b*******e 发帖数: 217 | 82 the agorithm using -1 mentioned by others earleir is the best.
Is the algorithm below oky? seems to me no extra space is needed though....
evyerthing can be in-place?
【在 b*******e 的大作中提到】 : build a min-heap in o(n). : query the min element. : query the two child ot he min element. : if the three elements not consecutive. find the missing interger already. : Otherwiese, go to the smaller child until the missing integer is found. o( : logn) : complexity = o(n) + o(logn)
|
a******e 发帖数: 710 | 83 min-heap的building time不是o(n logn) 么?
【在 b*******e 的大作中提到】 : build a min-heap in o(n). : query the min element. : query the two child ot he min element. : if the three elements not consecutive. find the missing interger already. : Otherwiese, go to the smaller child until the missing integer is found. o( : logn) : complexity = o(n) + o(logn)
|
c******5 发帖数: 84 | 84 public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length == 0) {// if A is empty, that means '1' is the missing
// positive
return 1;
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
i--;//continue doing A[i]
}
}
int j = 1;
while (j <= A.length && A[j - 1] == j) {
j++;
}
return j;
} |
m*********g 发帖数: 170 | 85 换换换换的思路:
假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3]
swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。
我们停止的地方就是要求的值。 |
b*******e 发帖数: 217 | 86
【在 a******e 的大作中提到】 : min-heap的building time不是o(n logn) 么?
|
b*******e 发帖数: 217 | 87 build heap is O(n). see CLS |
a***o 发帖数: 1182 | 88 如果s[1]一直不是1,停下来的条件是啥?
【在 m*********g 的大作中提到】 : 换换换换的思路: : 假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3] : swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。 : 我们停止的地方就是要求的值。
|
m*********g 发帖数: 170 | |
B********t 发帖数: 147 | 90 停下来的条件是 s[1] == s[s[1]]
【在 a***o 的大作中提到】 : 如果s[1]一直不是1,停下来的条件是啥?
|
|
|
m*****1 发帖数: 147 | 91 能解释一下你的思路吗??
missing
【在 c******5 的大作中提到】 : public int firstMissingPositive(int[] A) { : // Start typing your Java solution below : // DO NOT write main() function : if (A.length == 0) {// if A is empty, that means '1' is the missing : // positive : return 1; : } : for (int i = 0; i < A.length; i++) { : if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) { : int temp = A[A[i] - 1];
|
c******5 发帖数: 84 | 92 恩 我的思路是这样的:
不断的swap 碰到零或者负数就跳过,把正数A[i]swap到A[i]-1的位置,但要注意数组
的越界,所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap,所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4
【在 m*****1 的大作中提到】 : 能解释一下你的思路吗?? : : missing
|
t*********r 发帖数: 845 | 93 新手,欢迎大家拍砖
假设数组有n个大于0的而且不重复的整数,
(1) sum all elements, if sum=n(n+1)/2, then we know its n+1
(2) if not, compare with n/2, we will have two new arrays, one contains
elements <= n/2, one >n/2. Subtract the second one with n/2. find the sum of
first array, if sum=n'(n'+1)/2, the missing element must be in the second
array
(3) split the second one into two by comparing with n/4, and repeat again..
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
N*D 发帖数: 3641 | 94 俺也凑个热闹,贴个code
Run Status: Accepted!
Program Runtime: 564 milli secs
Progress: 156/156 test cases passed.
public class Solution {
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int length = A.length;
int i = 0;
while (i < length) {
// for pointer i, swap until the condition is broken.
while ((A[i] > 0) && (A[i] < length) && (A[i] != i+1)) {
if (A[A[i]-1] != A[i]) {
int tmp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = tmp;
} else {
break;
}
}
i++;
}
for (i = 0; i < length; i++) {
if (A[i] != i+1) {
return i+1;
}
}
return length+1;
}
}
Leetcode的test case真全啊,第一次的while loop忘记加判断碰上{1,1}就死循环了。
。。 |
j**7 发帖数: 143 | 95 public int firstMissingPositive(int[] input) {
// Start typing your Java solution below
// DO NOT write main() function
int length=input.length;
for(int i=0;i
{
while (input[i]!=i+1 && input[i]<=length &&input[i]>=1)
{
if(input[i]==input[input[i]-1])
break;
int temp=input[i];
input[i]=input[input[i]-1];
input[temp-1]=temp;
}
}
for(int i=0;i
{
if(input[i]!=i+1)
return i+1;
}
return length+1;
} |
A***o 发帖数: 358 | 96 O(n) time, O(n) space
int find(vector & input){
vector check;
check.resize(input.size(),0);
for(int i=0;i
if(input[i]>0 && input[i]<=input.size())
check[ input[i]-1 ]=input[i];
}
for(int i=0;i
if(check[i]==0)
return i+1;
}
return check.size()+1;
} |
b*******e 发帖数: 217 | 97 build a min-heap in o(n).
query the min element.
query the two child ot he min element.
if the three elements not consecutive. find the missing interger already.
Otherwiese, go to the smaller child until the missing integer is found. o(
logn)
complexity = o(n) + o(logn)
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
b*******e 发帖数: 217 | 98 the agorithm using -1 mentioned by others earleir is the best.
Is the algorithm below oky? seems to me no extra space is needed though....
evyerthing can be in-place?
【在 b*******e 的大作中提到】 : build a min-heap in o(n). : query the min element. : query the two child ot he min element. : if the three elements not consecutive. find the missing interger already. : Otherwiese, go to the smaller child until the missing integer is found. o( : logn) : complexity = o(n) + o(logn)
|
a******e 发帖数: 710 | 99 min-heap的building time不是o(n logn) 么?
【在 b*******e 的大作中提到】 : build a min-heap in o(n). : query the min element. : query the two child ot he min element. : if the three elements not consecutive. find the missing interger already. : Otherwiese, go to the smaller child until the missing integer is found. o( : logn) : complexity = o(n) + o(logn)
|
c******5 发帖数: 84 | 100 public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length == 0) {// if A is empty, that means '1' is the missing
// positive
return 1;
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
i--;//continue doing A[i]
}
}
int j = 1;
while (j <= A.length && A[j - 1] == j) {
j++;
}
return j;
} |
|
|
m*********g 发帖数: 170 | 101 换换换换的思路:
假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3]
swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。
我们停止的地方就是要求的值。 |
b*******e 发帖数: 217 | 102
【在 a******e 的大作中提到】 : min-heap的building time不是o(n logn) 么?
|
b*******e 发帖数: 217 | 103 build heap is O(n). see CLS |
a***o 发帖数: 1182 | 104 如果s[1]一直不是1,停下来的条件是啥?
【在 m*********g 的大作中提到】 : 换换换换的思路: : 假设数组S个数为n。我从1开始,S[1]如果是3,我就将它放到3的位置。即S[1]和s[3] : swap。再看s[1]的值,将其放到对应的位置。直到s[1]==1,我们看s[2]。以此类推。 : 我们停止的地方就是要求的值。
|
m*********g 发帖数: 170 | |
B********t 发帖数: 147 | 106 停下来的条件是 s[1] == s[s[1]]
【在 a***o 的大作中提到】 : 如果s[1]一直不是1,停下来的条件是啥?
|
m*****1 发帖数: 147 | 107 能解释一下你的思路吗??
missing
【在 c******5 的大作中提到】 : public int firstMissingPositive(int[] A) { : // Start typing your Java solution below : // DO NOT write main() function : if (A.length == 0) {// if A is empty, that means '1' is the missing : // positive : return 1; : } : for (int i = 0; i < A.length; i++) { : if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) { : int temp = A[A[i] - 1];
|
c******5 发帖数: 84 | 108 恩 我的思路是这样的:
不断的swap 碰到零或者负数就跳过,把正数A[i]swap到A[i]-1的位置,但要注意数组
的越界,所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap,所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4
【在 m*****1 的大作中提到】 : 能解释一下你的思路吗?? : : missing
|
t*********r 发帖数: 845 | 109 新手,欢迎大家拍砖
假设数组有n个大于0的而且不重复的整数,
(1) sum all elements, if sum=n(n+1)/2, then we know its n+1
(2) if not, compare with n/2, we will have two new arrays, one contains
elements <= n/2, one >n/2. Subtract the second one with n/2. find the sum of
first array, if sum=n'(n'+1)/2, the missing element must be in the second
array
(3) split the second one into two by comparing with n/4, and repeat again..
【在 d****o 的大作中提到】 : 这道题谁能解出来?(注意,这道题题意请理解清楚) : Given an unsorted integer array, find the first missing positive integer. : For example, : Given [1,2,0] return 3, : and [3,4,-1,1] return 2. : and [-3,-4,1,2,6,7] return 3 : Your algorithm should run in O(n) time and uses constant space.
|
N*D 发帖数: 3641 | 110 俺也凑个热闹,贴个code
Run Status: Accepted!
Program Runtime: 564 milli secs
Progress: 156/156 test cases passed.
public class Solution {
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int length = A.length;
int i = 0;
while (i < length) {
// for pointer i, swap until the condition is broken.
while ((A[i] > 0) && (A[i] < length) && (A[i] != i+1)) {
if (A[A[i]-1] != A[i]) {
int tmp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = tmp;
} else {
break;
}
}
i++;
}
for (i = 0; i < length; i++) {
if (A[i] != i+1) {
return i+1;
}
}
return length+1;
}
}
Leetcode的test case真全啊,第一次的while loop忘记加判断碰上{1,1}就死循环了。
。。 |
|
|
w***o 发帖数: 109 | 111 我用两个指针两遍夹的方法:
public int firstMissingPositive(int[] A) {
int l = 0, r = A.length-1;
while(l <= r) {
int x = A[l];
if(x == l+1) {
l++;
continue;
}
if(x <= l || x > r+1 || A[x-1] == x) {
A[l] = A[r--];
} else {
A[l] = A[x-1];
A[x-1] = x;
}
}
return l+1;
} |
o****d 发帖数: 2835 | 112 思路:
O(n)复杂度。一个长度为n的数组,缺失的第一个数一定是在[1,n+1]范围内。
把所有的数换到index对应的位置,比如把1放到A[1], 2放到A[2]...
这样做完之后 如果A[i]!=i的话 那就是i缺失了 (按上面换法,A[0]应该为n)
数字对调的判断条件中注意 1)如果i不在数组index范围内就skip 2)有duplicate的情
况下,A[i]=A[A[i]]也skip
class Solution {
public:
int firstMissingPositive(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for(int i=0; i
{
while(A[i]>=0 && A[i]
{ int tmp=A[A[i]]; A[A[i]]=A[i]; A[i]=tmp;}
}
for(int i=1; i
if(A[i]!=i) return i;
if(A[0]!=n) return n;
return n+1;
}
};
【在 B********t 的大作中提到】 : 停下来的条件是 s[1] == s[s[1]]
|