题目描述
输入一个整数数组, 实现一个函数来调整该数组中数字的顺序, 使得所有的奇数位于数组的前半部分, 所有的偶数位于数组的后半部分, 并保证奇数和奇数, 偶数和偶数之间的相对位置不变.
解法 1
最直接的思路是再构建一个新数组, 先遍历一遍原数组, 把其中的奇数依次添加到新数组中, 再遍历一遍原数组把其中的偶数依次添加到新数组中, 时间复杂度为 O(2n). 实现代码如下
实现代码
- public int[] reOrderArray2(int[] array)
- {
- int[] arr = new int[array.Length];
- int index = 0;
- for (int i = 0; i <array.Length; i++)
- {
- // 奇数
- if ((array[i] % 2) != 0)
- {
- arr[index] = array[i];
- index++;
- }
- }
- for (int i = 0; i < array.Length; i++)
- {
- // 偶数
- if ((array[i] % 2) == 0)
- {
- arr[index] = array[i];
- index++;
- }
- }
- return arr;
- }
解法 2
C# 的数组是不支持动态添加元素的, 我们可以使用泛型 List, 来实现在指定位置插入元素. 基本思路是遍历原数组, 依次将元素插入到 List 中, 如果是偶数元素, 默认插入到 List 的末尾. 如果是奇数元素, 则插入到所有的偶数元素之前(已插入的所有奇数元素之后), 因此需要记录最后插入的奇数元素的索引. 实现代码如下, 算法的时间复杂度是 O(n)
实现代码
- public int[] reOrderArray(int[] array)
- {
- List<int> list = new List<int>();
- // 最后插入奇数元素的索引
- int index = 0;
- foreach (int i in array)
- {
- if ((i % 2) == 0)
- list.Add(i);
- else
- {
- list.Insert(index, i);
- index++;
- }
- }
- return list.ToArray();
- }
解法 3
上面的两种解法都用到临时数组或 List, 空间复杂度是 O(n), 某些情况下可能希望空间复杂度越低越好. 下面这种解法虽然时间复杂度提高了, 但降低了空间复杂度, 不再需要额外的空间. 基本思路是遍历原数组, 如果遇到了奇数元素, 就将该元素向前移动, 该元素前面的偶数元素都依次向后移动.
举个例子: 比如数组{1, 2, 4, 3, 5}
遍历数组, 得到第一个元素是奇数 1, 其前面没有元素所以不做移动
第二个, 第三个是偶数, 不做处理.
第四个元素是奇数 3, 所以将 3 往前移动, 3 前面的偶数元素 {2, 4} 都向后移动. 移动后的数组为{1, 3, 2, 4, 5}
接着第五个元素是奇数 5, 所以将 5 往前移动, 5 前面的偶数元素 {2, 4} 都向后移动. 移动后的数组为{1, 3, 5, 2, 4}
可以这样理解, 每发现一个奇数时, 就将这个奇数移动到了它最终应该在的位置上.
实现代码
- public int[] reOrderArray(int[] array)
- {
- for(int i = 0; i <array.Length; i++)
- {
- if((array[i] % 2) != 0)
- {
- int temp = array[i];
- int j = i - 1;
- for(; j>= 0; j--)
- {
- if ((array[j] % 2) != 0)
- break;
- array[j + 1] = array[j];
- }
- array[j + 1] = temp;
- }
- }
- return array;
- }
来源: https://www.cnblogs.com/iwiniwin/p/11087105.html