算法题：将一维数组中的非零元素移动到数组前端（后端）

Bertha 。 2021-09-25 08:22 210阅读 0赞

### 文章目录 ###

*  1. 题目
 *   *  1.1. 输入
     *  1.2. 输出
 *  2. 算法一
 *   *  2.1. 分析
     *  2.2. 代码
     *  2.3. 结果
 *  3. 算法二
 *   *  3.1. 分析
     *  3.2. 代码
     *  3.3. 结果
 *  4. 非零元素移动到数组后端

# 1. 题目 #

现有一个一维数组  a = \[ 1 , 0 , 2 , 7 , 0 , 0 , 0 , 5 , 0 , − 3 \] a = \[1, 0, 2, 7, 0, 0, 0, 5, 0, -3\] a=\[1,0,2,7,0,0,0,5,0,−3\]，你需要将数组中非零元素移动到数组的前端，零元素在数组的后端。

## 1.1. 输入 ##

一个一维数组  a = \[ 1 , 0 , 2 , 7 , 0 , 0 , 0 , 5 , 0 , − 3 \] a = \[1, 0, 2, 7, 0, 0, 0, 5, 0, -3\] a=\[1,0,2,7,0,0,0,5,0,−3\]；

## 1.2. 输出 ##

a = \[ 1 , 2 , 7 , 5 , − 3 , 0 , 0 , 0 , 0 , 0 \] a = \[1, 2, 7, 5, -3, 0, 0, 0, 0, 0\] a=\[1,2,7,5,−3,0,0,0,0,0\]；

# 2. 算法一 #

## 2.1. 分析 ##

看到题目的第一想法就是，用另外一个和  a a a 等长度的数组来保存这些非零元素。

## 2.2. 代码 ##

public class Solution
    { 
    	/** * 一维数组中的非零元素前移. * * @param array 一维数组. * @return 非零元素前移后的一维数组. */
    	public static int[] nonZeroElementsMoveForward(int[] array)
    	{ 
    		// 边界检查
    		if (array == null || array.length == 0)
    			return array;
    		// 创建一个和 array 等长的数组，自动初始化为 0.
    		int[] changedArray = new int[array.length];
    		// 非零元素 array[i] 放入 changedArray 中的第 j 个位置.
    		for (int i = 0, j = 0; i < array.length; ++i)
    			if (array[i] != 0)
    				changedArray[j++] = array[i];
    		return changedArray;
    	}
    	
    	/** * 程序的入口. * * @param args 接收系统的参数 */
    	public static void main(String[] args)
    	{ 
    		int[] array = { 1, 0, 2, 7, 0, 0, 0, 5, 0, -3};
    		System.out.println(Arrays.toString(array));
    		array = nonZeroElementsMoveForward(array);
    		System.out.println(Arrays.toString(array));
    	}
    }

## 2.3. 结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]

# 3. 算法二 #

能不能不创建新的数组，直接在原数组上进行操作呢？

## 3.1. 分析 ##

在此基础上进行分析：  
输入中的元素 2，向前移动了 1 位，占据的是第一个 0 的位置（0 元素的位置是空闲的）；  
输入中的元素 7，向前移动了 1 位，占据的是上一个元素 2 空出来的位置（因为元素 2 向前移动了 1 位，所以这个位置空了出来）；  
输入中的元素 5，向前移动了 4 位，占据的是上一个元素 7 空出来的位置（因为元素 7 向前移动了 1 位，所以这个位置空了出来）；  
……

好像有一点点规律了。  
当遍历到数组中的非零元素的时候，假如知道上一个空闲位置就好了！！！

额外的一个指针就可以实现这样的功能。

遍历数组的指针 i，指向空闲位置的指针为 j。  
初始化，i = 0，j = 0。  
i 往后遍历，当 a\[i\] != 0 时，将 a\[i\] 放入 j 指示的位置上，即 a\[j\] = a\[i\]，然后 j 自增 1，指向下一个空闲位置。  
不过需要注意的是，当 i 完成遍历时，j 到 i 之间的元素，需要置为零。  
……

这种解法就是典型的**双指针法**。

## 3.2. 代码 ##

public class Solution
    { 
    	/** * 一维数组中的非零元素前移. * * @param array 一维数组 */
    	public static void nonZeroElementsMoveForward(int[] array)
    	{ 
    		// 边界检查
    		if (array == null || array.length == 0)
    			return;
    		// i 遍历数组，j 指示下一个空闲位置
    		int i, j;
    		// 将非零的元素 array[i] 放入 j 指示的位置中.
    		for (i = 0, j = 0; i < array.length; ++i)
    			if (array[i] != 0)
    				array[j++] = array[i];
    		// i 结束遍历时，j 之后的元素需要置为 0.
    		Arrays.fill(array, j, i, 0);
    	}
    	
    	/** * 程序的入口. * * @param args 接收系统的参数 */
    	public static void main(String[] args)
    	{ 
    		int[] array = { 1, 0, 2, 7, 0, 0, 0, 5, 0, -3};
    		System.out.println(Arrays.toString(array));
    		nonZeroElementsMoveForward(array);
    		System.out.println(Arrays.toString(array));
    	}
    }

## 3.3. 结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 1]

# 4. 非零元素移动到数组后端 #

思想和非零元素移动到数组前端一致，只需要将 i 和 j 从数组尾部进行遍历即可。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]: /images/20210923/7cafad8839a246f1be6262c00daefc66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 1]: /images/20210923/b8accb81ea4748fda435af727abce303.png