近期参与了几次面试。深圳的公司对于数据结构与算法比在厦门的公司更加的重视。很可惜平时工作中积累的不足,面试时都表现的不太好。
具体面试题可以简单的表现为:
输入数组 array = [1,2,3,0,4,5,6,0,7,8,9];
输出数组 array = [0,0,1,2,3,4,5,6,7,8,9];
面试官要求简单的执行一次循环并且在不增加空间的情况下完成。
以下是面试结束之后,隔天思考出来的具体解法:
NSArray * data = @[@"1",@"2",@"0",@"3",@"4",@"0",@"5",@"6",@"0",@"7",@"8",@"0",@"9"];
NSMutableArray * mudata = [NSMutableArray arrayWithArray:data];
int j=0;//已有0的数量，也等于已有0的位置.
for (int i =(int)data.count-1; i>=0; i--) {
int value = [mudata[i]intValue];
//1.便利。遇到数值为0的记录下来位置。
//2.遇到非0的数就跟记录下的0的位置进行交换。
if (value == 0) {
j++;
}
else
{
if (j>0) {
//说明此时有为0的数值。需要进行数值交换，›
int tempValue = [mudata[i]intValue];//当前的非0值.
//需要往后面移动的位数为j
mudata[i+j] = [NSString stringWithFormat:@"%d",tempValue];
mudata[i] = [NSString stringWithFormat:@"0"];
}
}
}
NSLog(@"0全部在前面拉%@",mudata);
通过双指针的技巧,完成功能。
Tips:如果需要将0值全部置于数组后部，非0值不改变排序置于前部。可以通过正序遍历数组,之后同样是记录下0值,当存在0值需要更换位置时,相应的通过i-j来找到需要替换数值的位置.
