c****a
发帖数: 50 | 1 给一个int数组，和一个数X，求K，使得A[0...K-1]里与X相等个数与A[K...N]不相等的
个数相等
要求输入int[] A,int X，求K，K不存在时返回-1
要求时间复杂度为O(N),空间复杂度为O(1)
例：{5,5,2,3,4,7,5}，K应为4，X为5时，A[0...3]里A[0]为5，A[1]为5，A[4...7]里A
[4],A[5]不等于5
感觉比较简单，当场写有些case总不能通过，郁闷
求比较简洁的实现 | C********e
发帖数: 492 | 2 扫描第一遍记下来多少个和X相等，多少个和X不等
扫第二遍到已经出现的X和剩下的和X不等个数相等的地方停下来就可以了。
里A
【在 c****a 的大作中提到】
: 给一个int数组，和一个数X，求K，使得A[0...K-1]里与X相等个数与A[K...N]不相等的
: 个数相等
: 要求输入int[] A,int X，求K，K不存在时返回-1
: 要求时间复杂度为O(N),空间复杂度为O(1)
: 例：{5,5,2,3,4,7,5}，K应为4，X为5时，A[0...3]里A[0]为5，A[1]为5，A[4...7]里A
: [4],A[5]不等于5
: 感觉比较简单，当场写有些case总不能通过，郁闷
: 求比较简洁的实现
| c*******g
发帖数: 332 | 3 I tried it as follows:
int getEqual(int A[], int n, int x) {
if (n<2) return -1;
int i=0, j=n-1;
int cnt_l, cnt_r;
cnt_l = A[0]==x?1:0;
cnt_r = A[n-1]!=x?1:0;
while (j-i>1) {
if (cnt_l
while(j-i>1 && A[i+1]!=x) {
i++;
}
if (j-i>1) {i++; cnt_l++;}
} else if(cnt_l>cnt_r) {
while(j-i>1 && A[j-1]==x) {
j--;
}
if (j-i>1) {j--; cnt_r++;}
} else {
if (A[i+1]==x && A[j-1]!=x) {i++;j--;cnt_l++;cnt_r++;}
else if (A[i+1]!=x && A[j-1]==x) {i++;j--;}
else if (A[i+1]==x) j--;
else i++;
}
}
return cnt_l==cnt_r?i+1:-1;
} | c******n
发帖数: 377 | 4 左右两个指针往中间扫，更新两个variable的值 : leftequal, rightnotequal 来决定
下一步如何挪动指针，知道指针相遇就可以了。 | z***b
发帖数: 127 | 5 1. 先从头到尾过一遍，看有多少个等于x的, 不等于x的数目始终保持0.
2. 再从尾部往头部走，依据元素的值更新num_equal 和 num_not_equal,直到两个数字
相等为止。
int Find_K(int *a, int n, int x) {
if ( n == 0 || n == 1)
return -1;
int i = 0, num_equal = 0, num_not_equal = 0;
for ( ; i < n; i++)
if (a[i] == x)
num_equal++;
if (num_equal == 0)
return n;
else {
i = n - 1;
while(i >= 0) {
if (a[i] == x) {
i--;
num_equal--;
if (num_equal == num_not_equal)
return i + 1;
} else {
i--;
num_not_equal++;
if (num_equal == num_not_equal)
return i + 1;
}
}
}
return -1;
} | s***c
发帖数: 639 | 6 这个K不应该就是K=N-nx么，nx是数组中X的个数
还是理解错了
里A
【在 c****a 的大作中提到】
: 给一个int数组，和一个数X，求K，使得A[0...K-1]里与X相等个数与A[K...N]不相等的
: 个数相等
: 要求输入int[] A,int X，求K，K不存在时返回-1
: 要求时间复杂度为O(N),空间复杂度为O(1)
: 例：{5,5,2,3,4,7,5}，K应为4，X为5时，A[0...3]里A[0]为5，A[1]为5，A[4...7]里A
: [4],A[5]不等于5
: 感觉比较简单，当场写有些case总不能通过，郁闷
: 求比较简洁的实现
| s******g
发帖数: 45 | 7 re
【在 c******n 的大作中提到】
: 左右两个指针往中间扫，更新两个variable的值 : leftequal, rightnotequal 来决定
: 下一步如何挪动指针，知道指针相遇就可以了。
| m*****k
发帖数: 731 | 8 java version of ztabb's idea:
public static int dividerIdx(int[] arr, int x){
if(arr==null || arr.length==0){
return -1;
}
int xCnt = 0;
for(int e : arr){
if(e == x){
xCnt++;
}
}
if(xCnt==0){
return -1;
}
int xSeen = 0;
for(int j = arr.length - 1; j>=0; j--){
if( arr[j] == x ){
xSeen++;
}
if(arr.length - j - xSeen == xCnt - xSeen){
return j;
}
}
return -1;
} | l*****a
发帖数: 14598 | 9 先扫一遍显然不能得分
【在 m*****k 的大作中提到】
: java version of ztabb's idea:
: public static int dividerIdx(int[] arr, int x){
:
: if(arr==null || arr.length==0){
: return -1;
: }
:
: int xCnt = 0;
: for(int e : arr){
: if(e == x){
| p*****2
发帖数: 21240 | 10
two pointers?
【在 l*****a 的大作中提到】
: 先扫一遍显然不能得分
| | | p*****2
发帖数: 21240 | 11 def split(arr:Array[Int], x: Int):Int = {
def loop(s: Int, c1: Int, e: Int, c2: Int): Int = {
if(s == e){
if(arr(s)==x && c1==c2+1 || arr(s)!=x && c1==c2+1) s-1
else if(arr(s)==x && c1+1==c2 || arr(s)!=x && c1==c2) s
else -1
}
else if(c1==c2) loop(s+1, c1+ (if(arr(s)==x) 1 else 0), e, c2)
else loop(s, c1, e-1, c2+ (if(arr(e)!=x) 1 else 0))
}
loop(0, 0, arr.length-1, 0)
} | z***b
发帖数: 127 | 12 你用c++写一个两个指针从两边移动的版本吧。我觉得这个写起来不好写对啊。。
【在 l*****a 的大作中提到】
: 先扫一遍显然不能得分
| p**p
发帖数: 742 | 13 试着做了一下，用左右两个指针，根据equal 和not equal 的值移动，请指教：
public static int getDividerIdx(int[] arr, int m) {
if(arr == null || arr.length == 0) {
throw new IllegalArgumentException("Input array cannot be null
or empty!");
}
int l = 0;
int r = arr.length-1;
int equal = 0;
int notEqual = arr[r] == m ? 0 : 1;
while(l <= r) {
if(l == r) {
return equal == notEqual ? l : -1;
}
if(equal > notEqual) {
r--;
notEqual += arr[r] == m ? 0 : 1;
} else if (equal < notEqual) {
equal += arr[l] == m ? 1 : 0;
l++;
} else { // equal == notEqual
if(arr[l] != m) {
l++;
} else {
r--;
notEqual += arr[r] == m ? 0 : 1;
}
}
}
return -1;
}
里A
【在 c****a 的大作中提到】
: 给一个int数组，和一个数X，求K，使得A[0...K-1]里与X相等个数与A[K...N]不相等的
: 个数相等
: 要求输入int[] A,int X，求K，K不存在时返回-1
: 要求时间复杂度为O(N),空间复杂度为O(1)
: 例：{5,5,2,3,4,7,5}，K应为4，X为5时，A[0...3]里A[0]为5，A[1]为5，A[4...7]里A
: [4],A[5]不等于5
: 感觉比较简单，当场写有些case总不能通过，郁闷
: 求比较简洁的实现
| l*********8
发帖数: 4642 | 14 int divid(int * A, int n, int x) {
if (!A || n <= 0) return -1;
int left = 0, right = n-1, banlance = 0;
while (left <= right) {
if (banlance < 0)
banlance += (A[left++] == x);
else if (banlance > 0)
banlance -= (A[right--] != x);
else if (A[left] != x)
++left;
else
banlance -= (A[right--] != x);
}
return !banlance ? left : -1;
}
里A
【在 c****a 的大作中提到】
: 给一个int数组，和一个数X，求K，使得A[0...K-1]里与X相等个数与A[K...N]不相等的
: 个数相等
: 要求输入int[] A,int X，求K，K不存在时返回-1
: 要求时间复杂度为O(N),空间复杂度为O(1)
: 例：{5,5,2,3,4,7,5}，K应为4，X为5时，A[0...3]里A[0]为5，A[1]为5，A[4...7]里A
: [4],A[5]不等于5
: 感觉比较简单，当场写有些case总不能通过，郁闷
: 求比较简洁的实现
| l*********8
发帖数: 4642 | 15 int divid(int * A, int n, int x) {
if (!A) return -1;
int left = 0, right = n-1, banlance = 0;
while (left <= right) {
if (banlance < 0 || (banlance == 0 && A[left] != x) )
banlance += (A[left++] == x);
else
banlance -= (A[right--] != x);
}
return !banlance ? left : -1;
}
【在 l*********8 的大作中提到】
: int divid(int * A, int n, int x) {
: if (!A || n <= 0) return -1;
: int left = 0, right = n-1, banlance = 0;
: while (left <= right) {
: if (banlance < 0)
: banlance += (A[left++] == x);
: else if (banlance > 0)
: banlance -= (A[right--] != x);
: else if (A[left] != x)
: ++left;
| d****n
发帖数: 233 | 16 int balancePoint(const vector &A, int T)
{
int n = A.size();
if ( n < 1) return -1;
int i = 1, j = n;
while(i < j) {
while(i < j && A[i-1] != T) i++;
if (i == j) return A[j-1] == T? i - 1 : i;
while(i < j && A[j-1] == T) j--;
if (i == j) return i-1 == 0? -1 : i - 1;
if (i + 1 == j) return i;
i++; j--;
}
int k = A[i-1] == T? i-1 : i;
return k == 0? -1 : k;
}
【在 l*********8 的大作中提到】
: int divid(int * A, int n, int x) {
: if (!A) return -1;
: int left = 0, right = n-1, banlance = 0;
: while (left <= right) {
: if (banlance < 0 || (banlance == 0 && A[left] != x) )
: banlance += (A[left++] == x);
: else
: banlance -= (A[right--] != x);
: }
: return !banlance ? left : -1;
| l*********u
发帖数: 19053 | 17 nx包括数组中，后半段X的个数，不能算的。
【在 s***c 的大作中提到】
: 这个K不应该就是K=N-nx么，nx是数组中X的个数
: 还是理解错了
:
: 里A
|
|
