a********r
发帖数: 218 | 1 要我优化下面的程序， 怎么优化呀？
int maxDiff(vector& A)
{
int N = A.size();
int result = 0;
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
if (A[i] != A[j])
result = max(result, j - i);
return result;
} |
k****r
发帖数: 421 | |
s***5
发帖数: 2136 | 3 这么土鳖的问题，太丢人了
两个指针从两头扫一遍搞定。 |
c**s
发帖数: 159 | 4 问题转化
对每个 i , minj 使得 A[i] != A［j]
当然还要求maxj
求minj的话 其实就是对不等于A[0]的A[I],
j取0
如果A［i]==A［0］ j取最小的不等于A［0］的下标
类似可求maxj.
或者把数组翻转再求一次 minj
如此扫描两次即可
【在 a********r 的大作中提到】
: 要我优化下面的程序， 怎么优化呀？
: int maxDiff(vector& A)
: {
: int N = A.size();
: int result = 0;
: for (int i = 0; i < N; i++)
: for (int j = i; j < N; j++)
: if (A[i] != A[j])
: result = max(result, j - i);
: return result;
|
f*******t
发帖数: 7549 | 5 这不就是扫一遍找出max和min，相减得result
O(n^2)优化到O(n) |
s***5
发帖数: 2136 | 6 多少人连题都没看懂？面试的话上面基本都要被刷掉了。找的是不相等的元素在数组中
的最远距离(index之差），没什么min，max。就从两端往中间扫，直到找到一对不相等
的。 |
Y********g
发帖数: 1 | 7 Re
【在 s***5 的大作中提到】
: 多少人连题都没看懂？面试的话上面基本都要被刷掉了。找的是不相等的元素在数组中
: 的最远距离(index之差），没什么min，max。就从两端往中间扫，直到找到一对不相等
: 的。
|
W***u
发帖数: 1 | 8 题目看懂了，解法错误
index之差最大是n-1, 最小是1
在一个for loop里，x 范围从n-1到1，遍历所有距离为x 的index pair，找到就返回
【在 s***5 的大作中提到】
: 多少人连题都没看懂？面试的话上面基本都要被刷掉了。找的是不相等的元素在数组中
: 的最远距离(index之差），没什么min，max。就从两端往中间扫，直到找到一对不相等
: 的。
|
W***u
发帖数: 1 | |
A***g
发帖数: 1816 | 10 可以非常简单的做法
1. 看两头，如果不等，return n-1
2. 如果两头相等，loop一遍，每次看到第一个和不等的 i，返回max（i, n-i) |
b******g
发帖数: 77 | 11 Something like:
int maxDiff(vector& A)
{
int N = A.size();
if (N < 2) return 0;
for (int i = 0, j = N-1; i < j;) {
if (A[i] != A[j]) return j - i;
if (A[i] == A[i + 1]) { ++i }
else { --j }
}
return 0;
} |
a********r
发帖数: 218 | 12 验证过了，100分。
膜拜大牛！
【在 b******g 的大作中提到】
: Something like:
: int maxDiff(vector& A)
: {
: int N = A.size();
: if (N < 2) return 0;
: for (int i = 0, j = N-1; i < j;) {
: if (A[i] != A[j]) return j - i;
: if (A[i] == A[i + 1]) { ++i }
: else { --j }
: }
|
b****h
发帖数: 2105 | 13 他是错的
【在 a********r 的大作中提到】
: 验证过了，100分。
: 膜拜大牛！
|
X****N
发帖数: 376 | 14 int maxDiff(vector& A)
{
if (A.size() <= 1) {
return 0;
}
int head = 0;
int tail = A.size() - 1;
if (A[head] != A[tail]) {
return tail - head;
}
int first_diff = head; // first diff from head
while (first_diff < tail && A[first_diff] == A[head]) { first_diff++ };
if (first_diff >= tail) {
// no diff element
return 0;
}
int last_diff = tail; // first diff from tail
while (last_diff > 0 && A[last_diff] == A[tail]) { last_diff-- };
return max(
last_diff-head, // from head to last diff
tail-first_diff // from first diff to tail
);
} |
f*******t
发帖数: 7549 | 15 我觉得if (A[i] == A[i + 1]) { ++i }是错的
【在 b****h 的大作中提到】
: 他是错的
|
a********r
发帖数: 218 | 16 我用这个
vector A = {4, 5, 2, 2, 6, 6, 4};
验证了一下，是对的。 你能给个例子说明他是错的吗？
【在 f*******t 的大作中提到】
: 我觉得if (A[i] == A[i + 1]) { ++i }是错的
|
i******u
发帖数: 1 | 17 这个还是要扫很多重复的。
难道不是第一个从头扫，第二个也是从头扫，然后扫到不等后，直接修改第一个的
index。就是加一句 i=j;
【在 W***u 的大作中提到】
: 题目看懂了，解法错误
: index之差最大是n-1, 最小是1
: 在一个for loop里，x 范围从n-1到1，遍历所有距离为x 的index pair，找到就返回
|
W***u
发帖数: 1 | 18 Try 4,5,4,4,4,4,4
【在 a********r 的大作中提到】
: 我用这个
: vector A = {4, 5, 2, 2, 6, 6, 4};
: 验证了一下，是对的。 你能给个例子说明他是错的吗？
|
W***u
发帖数: 1 | 19 i 和j不能同时动，必需要两个loop
【在 i******u 的大作中提到】
: 这个还是要扫很多重复的。
: 难道不是第一个从头扫，第二个也是从头扫，然后扫到不等后，直接修改第一个的
: index。就是加一句 i=j;
|
f*******t
发帖数: 7549 | 20 {1,1,1,2,1} return 1
正确结果应该是3
我觉得这题的解可能还是要O(n^2)复杂度，代码可以优化一些
【在 a********r 的大作中提到】
: 我用这个
: vector A = {4, 5, 2, 2, 6, 6, 4};
: 验证了一下，是对的。 你能给个例子说明他是错的吗？
|
N**********n
发帖数: 1 | 21 two pointers O(N)
int maxDiff(vector& A)
{
int N = A.size();
int result = 0;
if(A[0] != A[N-1])
return N-1;
int i = 0, j = N-1;
while(i <= j && A[i] == A[0])
i++;
while(i <= j && A[j] == A[0])
j--;
if(i > j)
return 0;
return max(N-1-i, j);
} |
n******g
发帖数: 2201 | 22 O(n) two-pass:
https://www.geeksforgeeks.org/maximum-distance-between-two-unequal-elements/
【在 f*******t 的大作中提到】
: {1,1,1,2,1} return 1
: 正确结果应该是3
: 我觉得这题的解可能还是要O(n^2)复杂度，代码可以优化一些
|
w*****e
发帖数: 721 | 23 int maxDiff(vector& A)
{
int N = A.size();
int result = 0;
if(A[0] != A[N-1])
return N-1;
int i = 0, j = N-1;
while(i <= j && A[i] == A[j]){
if (A[i] != A[i+1] || A[j] != A[j-1])
return (j-1-i);
}
i++; j--;
}
if(i > j)
return 0;
return max(N-1-i, j);
} |
n******g
发帖数: 2201 | 24 def maxDistance(A):
if A[0] != A[-1]:
return len(A) - 1
res = 0
for i, a in enumerate(A):
if a != A[0]:
res = max(i, len(A) - i - 1)
return res
based on AMang's idea
【在 A***g 的大作中提到】
: 可以非常简单的做法
: 1. 看两头，如果不等，return n-1
: 2. 如果两头相等，loop一遍，每次看到第一个和不等的 i，返回max（i, n-i)
|
b*f
发帖数: 212 | 25 这样应该没错吧：
5 int maxDiff(vector& A){
6
7 int N=A.size();
8 if(N<2) return 0;
9 for(int i=0, j=N-1; i
10 if(A[i]!=A[j])
11 return j-i;
12 else if(A[i]==A[i+1])
13 j--;
14 else
15 return j-i-1;
16 }
17
18
19 return 0;
20 } |
s***5
发帖数: 2136 | 26 叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要n^2，无语了。
int maxIndexDiff(vector nums) {
int n = nums.size();
if(n == 0) return 0;
if(nums[0] != nums[n - 1])
return n - 1;
int i = 0;
while(i < n - 1 && nums[i] == nums[i + 1]) i++;
if(i == n - 1) return 0;
return max(i + 1, n - 2 - i);
} |
f*******t
发帖数: 7549 | 27 唉，刷题不能停，一个月不刷大脑就生锈啦
了。
【在 s***5 的大作中提到】
: 叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要n^2，无语了。
: int maxIndexDiff(vector nums) {
: int n = nums.size();
: if(n == 0) return 0;
: if(nums[0] != nums[n - 1])
: return n - 1;
: int i = 0;
: while(i < n - 1 && nums[i] == nums[i + 1]) i++;
: if(i == n - 1) return 0;
: return max(i + 1, n - 2 - i);
|
l******n
发帖数: 9344 | 28 你这个是从左边开始扫，也可以两边往中间扫
def indexDiff(vec):
n = len(vec)
if n <= 1:
return(0)
l, r = 0, n-1
while l < r:
if vec[l] != vec[r]:
return(r-l)
if vec[l+1] != vec[l] or vec[r-1] != vec[l]:
return(r-l-1)
else:
l += 1
r -= 1
return(0)
了。
【在 s***5 的大作中提到】
: 叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要n^2，无语了。
: int maxIndexDiff(vector nums) {
: int n = nums.size();
: if(n == 0) return 0;
: if(nums[0] != nums[n - 1])
: return n - 1;
: int i = 0;
: while(i < n - 1 && nums[i] == nums[i + 1]) i++;
: if(i == n - 1) return 0;
: return max(i + 1, n - 2 - i);
|
n******g
发帖数: 2201 | 29 vec[l+1] 会指针越界，这种情况一般要加上
while l + 1 < r and vec[l+1] ...
【在 l******n 的大作中提到】
: 你这个是从左边开始扫，也可以两边往中间扫
: def indexDiff(vec):
: n = len(vec)
: if n <= 1:
: return(0)
:
: l, r = 0, n-1
: while l < r:
: if vec[l] != vec[r]:
: return(r-l)
|
l******n
发帖数: 9344 | 30 只要有两个元素就不会越界的。把前面的 n== 0条件, 改成n<=1就好了
【在 n******g 的大作中提到】
: vec[l+1] 会指针越界，这种情况一般要加上
: while l + 1 < r and vec[l+1] ...
|
l**********0
发帖数: 150 | 31 试试这个例子。[1,1,1,1,1,1,0,1,1,2,1]
目前只有一个人做对了。
了。
【在 s***5 的大作中提到】
: 叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要n^2，无语了。
: int maxIndexDiff(vector nums) {
: int n = nums.size();
: if(n == 0) return 0;
: if(nums[0] != nums[n - 1])
: return n - 1;
: int i = 0;
: while(i < n - 1 && nums[i] == nums[i + 1]) i++;
: if(i == n - 1) return 0;
: return max(i + 1, n - 2 - i);
|
s***5
发帖数: 2136 | 32 难道答案不是6？难道叔的code在这个case不work？再度无语了。
【在 l**********0 的大作中提到】
: 试试这个例子。[1,1,1,1,1,1,0,1,1,2,1]
: 目前只有一个人做对了。
:
: 了。
|
a********r
发帖数: 218 | 33 答案是9， 25楼对的
【在 s***5 的大作中提到】
: 难道答案不是6？难道叔的code在这个case不work？再度无语了。
|
s***5
发帖数: 2136 | 34 还是应该用两个指针往中间扫，想着简化成一个指针但是miss了cases。
int maxIndexDiff(vector nums) {
int n = nums.size();
if(n <= 1) return 0;
if(nums[0] != nums[n - 1])
return n - 1;
int i = 0;
while(i < n - 1 && nums[i] == nums[i + 1]) i++;
if(i == n - 1) return 0;
int j = n - 1;
while(j > i + 1 && nums[j] == nums[j - 1]) j--;
return max(max(i + 1, n - 2 - i), max(j - 1, n - j));
}
【在 a********r 的大作中提到】
: 答案是9， 25楼对的
|
J*****4
发帖数: 1 | 35 就一个指针应该也可以,数组长度N
1i=0开始，比较是否与数组最后一个数不一样，如果不一样则返回max(i,N-1-i)
2将i加1,进入第一步
循环结束还没返回则返回0
因为不可能存在中间区段状况。
刚看到10楼算法和我一样。
我大概说下为何不存在中间区段状况，假设存在最大中间区段i,j，则意味这个中间区
段的左边k
。同理可以推出这个中间区段的右边m>j所有数字A[m]必然等于A[i]. 那么整个数组
第一
个和最后一个就必然不一样，但这同样违背最大中间段是i, j 的前提。所以不同的两个
数其中一个必然是第一个或最后一个。 |
m****w
发帖数: 1 | 36 for(i=0;i<=num.size()/2;i十十){
if(num[0]!=num[num.size()-i-1] ||
num[i]!=num[num.size()-1])
return num.size()-i-1;
}
return 0; |
h**6
发帖数: 4160 | |
