输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分。
这道题出自 《剑指Offer》,这道题有两个版本也就是还有个进阶版本。
普通版本:使所有奇数在数组的前半部分,偶数在数组的后半部分
普通版思路:进阶版本:使使所有奇数在数组的前半部分,偶数在数组的后半部分,并且保证所有奇数和偶数的先后顺序不变。
普通版本解法其实比较简单,指需要定义两个指针。一个指向数组的第一个元素,一个指向数组的最后的一个元素。
第一个指针从前往后找偶数,第二个指针从后往前找奇数。然后交换两个指针指向的元素,当两个指针相遇时就交换完成。
void swap(int* a,int* b); int* exchange(int* nums, int numsSize, int* returnSize){ int left = 0; int right = numsSize-1; while (left < right) { //从前往后找偶数 while ( (nums[left]&1) == 1 && left < right) { left++; } //从后往前找奇数 while ( (nums[right]&1) != 1 && left < right ) { right--; } //当left指向偶数,right指向奇数 swap(&nums[left],&nums[right]); left++; right--; } *returnSize = numsSize; return nums; } void swap(int* a,int* b) { int tmp = *a; *a = *b; *b = tmp; }Java代码
class Solution { public int[] exchange(int[] nums) { if (nums == null || nums.length == 0) { return nums; } int left = 0; int right = nums.length-1; while (left < right) { //从前往后找偶数 while (left < right && (nums[left]&1) == 1) { left++; } //从后往前找奇数 while (left < right && (nums[right]&1) != 1) { right--; } //当left指向偶数,right指向奇数 int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp; left++; right--; } return nums; } }进阶版思路:
1.定义一个index变量记录当前已经找到奇数的最后一个奇数的后一个下标,刚开始不知道第一个奇数是谁,从0开始
2.定义一个 i 从头开始遍历数组判断是否是奇数,如果判读是奇数,就把这个奇数存入tmp变量里
3.再定义一个 j 下标等于 i ,让后 j从后往前走不断把前面的偶数往后移动,因为前面的判断已经是确定了 i 前面的数已经不是奇数了。
C语言代码4.当 j 不再大于 index的时候,结束移动。再把 tmp里的数放入index下标的位置,再让index++,这样index就一直记录着前半部分已经找到奇数的后一个下标,找到一个奇数就把奇数放到index位置。偶数是从后往前移动的,就不会存在数字的先后顺序交换问题
int* reOrderArray(int* array, int arrayLen, int* returnSize ) { // write code here int index = 0; for (int i = 0; i < arrayLen; i++) { if ((array[i]&1) == 1) { int tmp = array[i]; int j = i; while (j > index) { array[j] = array[j-1]; j--; } array[index++] = tmp; } } *returnSize = arrayLen; return array; }Java代码
public int[] exchange(int[] nums) { if (nums == null || nums.length == 0) { return nums; } //index用来记录当前前半部分已经找到的奇数的后面一个下标 int index = 0; for (int i = 0; i < nums.length; i++) { //判断是否是奇数 if ((nums[i]&1) == 1) { //tmp存放这个奇数 int tmp = nums[i]; //把奇数前面的偶数全部往后移一个位置 int j = i; while (j > index) { nums[j] = nums[j-1]; j--; } //把tmp里的奇数放到index位置 nums[index++] = tmp; } } return nums; }
题目链接 调整数组顺序使奇数位于偶数前面
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)