Redian新闻
>
今天遇到的一个面试题
avatar
今天遇到的一个面试题# JobHunting - 待字闺中
c*a
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总不能通过,郁闷
求比较简洁的实现
avatar
C*e
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总不能通过,郁闷
: 求比较简洁的实现

avatar
c*g
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;
}
avatar
c*n
4
左右两个指针往中间扫,更新两个variable的值 : leftequal, rightnotequal 来决定
下一步如何挪动指针,知道指针相遇就可以了。
avatar
z*b
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;
}
avatar
s*c
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总不能通过,郁闷
: 求比较简洁的实现

avatar
s*g
7
re

【在 c******n 的大作中提到】
: 左右两个指针往中间扫,更新两个variable的值 : leftequal, rightnotequal 来决定
: 下一步如何挪动指针,知道指针相遇就可以了。

avatar
m*k
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;
}
avatar
l*a
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){

avatar
p*2
10

two pointers?

【在 l*****a 的大作中提到】
: 先扫一遍显然不能得分
avatar
p*2
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)
}
avatar
z*b
12
你用c++写一个两个指针从两边移动的版本吧。我觉得这个写起来不好写对啊。。

【在 l*****a 的大作中提到】
: 先扫一遍显然不能得分
avatar
p*p
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总不能通过,郁闷
: 求比较简洁的实现

avatar
l*8
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总不能通过,郁闷
: 求比较简洁的实现

avatar
l*8
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;

avatar
d*n
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;

avatar
l*u
17
nx包括数组中,后半段X的个数,不能算的。

【在 s***c 的大作中提到】
: 这个K不应该就是K=N-nx么,nx是数组中X的个数
: 还是理解错了
:
: 里A

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。