b*******y
发帖数: 1240 | 1 Given a table A of N integers from 0 to N-1 calculate the smallest such inde
x P, that that {A[0],...,A[N-1]} = {A[0],...,A[P]}.
测试的时候timeout了，可能时间复杂度过高，不知道怎么改。
int ps ( int[] A ) {
// write your code here
int size = A.length;//数组长度
int p = 0;//返回的index
int j = 1;//用于比较的index，与A[0]-A[j-1]比较，看是否存在重复
while(j < size)
{
int ex = 0; //记录是否出现重复
for(int i = 0; i < j; i++)
{
if(A[i] == A[j])
{
ex = 1;
break;
}//出现重复值
}
if(ex == 0)//无重复值
p = j;
j++;
}
return p;
} |
m****i
发帖数: 650 | 2 起码解释一下你定义的变量的作用。
这样的代码没人愿意看 |
b*******y
发帖数: 1240 | 3 好，刚刚改了一下
【在 m****i 的大作中提到】
: 起码解释一下你定义的变量的作用。
: 这样的代码没人愿意看
|
m****i
发帖数: 650 | 4 没理解你的代买作用
比如 数组 1 2 3 4 3 5 6
你的p是返回那个，我的理解是返回2 |
b*******y
发帖数: 1240 | 5 p应该返回6
某一个数组A[0],...A[n-1]
存在其中一个子数组A[0]...A[p]
使得子数组包含原数组的所有值
【在 m****i 的大作中提到】
: 没理解你的代买作用
: 比如 数组 1 2 3 4 3 5 6
: 你的p是返回那个，我的理解是返回2
|
m****i
发帖数: 650 | |
b*******y
发帖数: 1240 | 7 返回4
因为1 2 3 4 包含了 3
【在 m****i 的大作中提到】
: 比如 数组 1 2 3 4 3
: 返回哪个
|
m****i
发帖数: 650 | 8
首先你代码不对，你代买会返回3
其次，我觉的你要就求就是求数据最后一个是不是重复了，重复了就往左边继续找直到
找到不重复的返回。
如果我理解对了，你可以从后面开始查找，快很多
【在 b*******y 的大作中提到】
: 返回4
: 因为1 2 3 4 包含了 3
|
b*******y
发帖数: 1240 | 9 返回的是index
如果数组是1 2 3 4
那么4所在的index就是3啊
【在 m****i 的大作中提到】
:
: 首先你代码不对，你代买会返回3
: 其次，我觉的你要就求就是求数据最后一个是不是重复了，重复了就往左边继续找直到
: 找到不重复的返回。
: 如果我理解对了，你可以从后面开始查找，快很多
|
b*******y
发帖数: 1240 | 10 你这个是要快
那时间复杂度怎么算？
【在 m****i 的大作中提到】
:
: 首先你代码不对，你代买会返回3
: 其次，我觉的你要就求就是求数据最后一个是不是重复了，重复了就往左边继续找直到
: 找到不重复的返回。
: 如果我理解对了，你可以从后面开始查找，快很多
|
r*****l
发帖数: 2859 | 11 先小改一下：
In the for loop: i < j => i < p
A[i] == A[j] => A[i].intValue() == A[j].intValue().
no need to use "ex"
remember to check null if null value allowed.
inde
【在 b*******y 的大作中提到】
: Given a table A of N integers from 0 to N-1 calculate the smallest such inde
: x P, that that {A[0],...,A[N-1]} = {A[0],...,A[P]}.
: 测试的时候timeout了，可能时间复杂度过高，不知道怎么改。
: int ps ( int[] A ) {
: // write your code here
: int size = A.length;//数组长度
: int p = 0;//返回的index
: int j = 1;//用于比较的index，与A[0]-A[j-1]比较，看是否存在重复
: while(j < size)
: {
|
r*****l
发帖数: 2859 | 12 Another suggestion: you can sacrifice space for time, like using hash.
【在 r*****l 的大作中提到】
: 先小改一下：
: In the for loop: i < j => i < p
: A[i] == A[j] => A[i].intValue() == A[j].intValue().
: no need to use "ex"
: remember to check null if null value allowed.
:
: inde
|
