面试题-数组排序。(将数组内0值数置于前部,非0值不改变排列顺序

近期参与了几次面试。深圳的公司对于数据结构与算法比在厦门的公司更加的重视。很可惜平时工作中积累的不足,面试时都表现的不太好。

具体面试题可以简单的表现为:
输入数组 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来找到需要替换数值的位置.