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; }
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 ); }
要我优化下面的程序， 怎么优化呀？
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;
}
可以优化到线性吧。。。。。。
这么土鳖的问题，太丢人了
两个指针从两头扫一遍搞定。
扫一遍找出min和max即可
问题转化
对每个 i , minj 使得 A[i] != A［j]
当然还要求maxj
求minj的话 其实就是对不等于A[0]的A[I],
j取0
如果A［i]==A［0］ j取最小的不等于A［0］的下标
类似可求maxj.
或者把数组翻转再求一次 minj
如此扫描两次即可
【 在 antilawyer (antilawyer) 的大作中提到: 】
: 要我优化下面的程序， 怎么优化呀？
:
:
: 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;
: }
这不就是扫一遍找出max和min，相减得result
O(n^2)优化到O(n)
多少人连题都没看懂？面试的话上面基本都要被刷掉了。找的是不相等的元素在数组中的最远距离(index之差），没什么min，max。就从两端往中间扫，直到找到一对不相等的。
Re
【 在 sue85 (家有小灰兔) 的大作中提到: 】
: 多少人连题都没看懂？面试的话上面基本都要被刷掉了。找的是不相等的元素在数组中
: 的最远距离(index之差），没什么min，max。就从两端往中间扫，直到找到一对不相等
: 的。
题目看懂了，解法错误
index之差最大是n-1, 最小是1
在一个for loop里，x 范围从n-1到1，遍历所有距离为x 的index pair，找到就返回
【 在 sue85 (家有小灰兔) 的大作中提到: 】
: 多少人连题都没看懂？面试的话上面基本都要被刷掉了。找的是不相等的元素在数组中
: 的最远距离(index之差），没什么min，max。就从两端往中间扫，直到找到一对不相等
: 的。
sliding window 变种
可以非常简单的做法
1. 看两头，如果不等，return n-1
2. 如果两头相等，loop一遍，每次看到第一个和不等的 i，返回max（i, n-i)
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;
}
验证过了，100分。
膜拜大牛！
【 在 beidapig (做人要谦虚) 的大作中提到: 】
: 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 }
: }
: ...................
他是错的
【 在 antilawyer (antilawyer) 的大作中提到: 】
: 验证过了，100分。
: 膜拜大牛！
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
);
}
我觉得if (A[i] == A[i + 1]) { ++i }是错的
【 在 btfath (btfd) 的大作中提到: 】
: 他是错的
我用这个
vector A = {4, 5, 2, 2, 6, 6, 4};
验证了一下，是对的。 你能给个例子说明他是错的吗？
【 在 fantasist (一) 的大作中提到: 】
: 我觉得if (A[i] == A[i + 1]) { ++i }是错的
这个还是要扫很多重复的。
难道不是第一个从头扫，第二个也是从头扫，然后扫到不等后，直接修改第一个的
index。就是加一句 i=j;
【 在 Wagyu (瓦古) 的大作中提到: 】
: 题目看懂了，解法错误
: index之差最大是n-1, 最小是1
: 在一个for loop里，x 范围从n-1到1，遍历所有距离为x 的index pair，找到就返回
Try 4,5,4,4,4,4,4
【 在 antilawyer (antilawyer) 的大作中提到: 】
: 我用这个
: vector A = {4, 5, 2, 2, 6, 6, 4};
: 验证了一下，是对的。 你能给个例子说明他是错的吗？
i 和j不能同时动，必需要两个loop
【 在 indejavu (life cycles) 的大作中提到: 】
: 这个还是要扫很多重复的。
: 难道不是第一个从头扫，第二个也是从头扫，然后扫到不等后，直接修改第一个的
: index。就是加一句 i=j;
{1,1,1,2,1} return 1
正确结果应该是3
我觉得这题的解可能还是要O(n^2)复杂度，代码可以优化一些
【 在 antilawyer (antilawyer) 的大作中提到: 】
: 我用这个
: vector A = {4, 5, 2, 2, 6, 6, 4};
: 验证了一下，是对的。 你能给个例子说明他是错的吗？
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);
}
O(n) two-pass:
https://www.geeksforgeeks.org/maximum-distance-between-two-unequal-elements/
【 在 fantasist (一) 的大作中提到: 】
: {1,1,1,2,1} return 1
: 正确结果应该是3
: 我觉得这题的解可能还是要O(n^2)复杂度，代码可以优化一些
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);
}
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
【 在 AMang (阿忙) 的大作中提到: 】
: 可以非常简单的做法
: 1. 看两头，如果不等，return n-1
: 2. 如果两头相等，loop一遍，每次看到第一个和不等的 i，返回max（i, n-i)
这样应该没错吧：
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; i10 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 }
叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要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);
}
唉，刷题不能停，一个月不刷大脑就生锈啦
【 在 sue85 (家有小灰兔) 的大作中提到: 】
: 叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要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);
: ...................
你这个是从左边开始扫，也可以两边往中间扫
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)
【 在 sue85 (家有小灰兔) 的大作中提到: 】
: 叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要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);
: ...................
vec[l+1] 会指针越界，这种情况一般要加上
while l + 1 < r and vec[l+1] ...
【 在 longtian (有人的地方,就有江湖) 的大作中提到: 】
: 你这个是从左边开始扫，也可以两边往中间扫
: def indexDiff(vec):
: n = len(vec)
: if n == 0:
: return(0)
:
: l, r = 0, n-1
: while l < r:
: if vec[l] != vec[r]:
: return(r-l)
: ...................
只要有两个元素就不会越界的。把前面的 n== 0条件, 改成n<=1就好了
【 在 nostring (尼) 的大作中提到: 】
: vec[l+1] 会指针越界，这种情况一般要加上
: while l + 1 < r and vec[l+1] ...
试试这个例子。[1,1,1,1,1,1,0,1,1,2,1]
目前只有一个人做对了。
【 在 sue85 (家有小灰兔) 的大作中提到: 】
: 叔在最上面就指出两个指针往中间扫，居然有人说是错的，有人说还是要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);
: ...................
难道答案不是6？难道叔的code在这个case不work？再度无语了。
【 在 lestrois2000 (lestrois2000) 的大作中提到: 】
: 试试这个例子。[1,1,1,1,1,1,0,1,1,2,1]
: 目前只有一个人做对了。
: 了。
答案是9， 25楼对的
【 在 sue85 (家有小灰兔) 的大作中提到: 】
: 难道答案不是6？难道叔的code在这个case不work？再度无语了。
还是应该用两个指针往中间扫，想着简化成一个指针但是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));
}
【 在 antilawyer (antilawyer) 的大作中提到: 】
: 答案是9， 25楼对的
就一个指针应该也可以,数组长度N
1i=0开始，比较是否与数组最后一个数不一样，如果不一样则返回max(i,N-1-i)
2将i加1,进入第一步
循环结束还没返回则返回0
因为不可能存在中间区段状况。
刚看到10楼算法和我一样。
我大概说下为何不存在中间区段状况，假设存在最大中间区段i,j，则意味这个中间区
段的左边k<i所有数字A[k]必然等于A[j],如果不等则违背最大中间段是i, j 的前提。同理可以推出这个中间区段的右边m>j所有数字A[m]必然等于A[i]. 那么整个数组第一
个和最后一个就必然不一样，但这同样违背最大中间段是i, j 的前提。所以不同的两个
数其中一个必然是第一个或最后一个。
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;
数学上证明，i、j至少一个在两头。完事