今天遇到的一个面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

今天遇到的一个面试题

今天遇到的一个面试题# JobHunting - 待字闺中

c*a2014-12-05 08:12

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*e2014-12-05 08:12

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*g2014-12-05 08:12

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_lwhile(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*n2014-12-05 08:12

4 楼

左右两个指针往中间扫，更新两个variable的值 : leftequal, rightnotequal 来决定
下一步如何挪动指针，知道指针相遇就可以了。

z*b2014-12-05 08:12

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*c2014-12-05 08:12

6 楼

这个K不应该就是K=N-nx么，nx是数组中X的个数
还是理解错了

里A

【在 c****a 的大作中提到】

s*g2014-12-05 08:12

7 楼

re

【在 c******n 的大作中提到】

: 左右两个指针往中间扫，更新两个variable的值 : leftequal, rightnotequal 来决定
: 下一步如何挪动指针，知道指针相遇就可以了。

m*k2014-12-05 08:12

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*a2014-12-05 08:12

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*22014-12-05 08:12

10 楼

two pointers?

【在 l*****a 的大作中提到】

: 先扫一遍显然不能得分

p*22014-12-05 08:12

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*b2014-12-05 08:12

12 楼

你用c++写一个两个指针从两边移动的版本吧。我觉得这个写起来不好写对啊。。

【在 l*****a 的大作中提到】

: 先扫一遍显然不能得分

p*p2014-12-05 08:12

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 的大作中提到】

l*82014-12-05 08:12

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 的大作中提到】

l*82014-12-05 08:12

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*n2014-12-05 08:12

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;