剑指 Offer 21. 调整顺序使奇数位于偶数前面


categories: [Blog,Algorithm]


剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

难度简单 84
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

示例:
输入:nums = [1,2,3,4]
输出:[1,3,2,4] 
注:[3,1,2,4] 也是正确的答案之一。

class Solution {
    public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while(i < j) &#123;
            while(i < j && (nums[i] & 1) == 1) i++;
            System.out.println("i="+i+",j="+j);
            while(i < j && (nums[j] & 1) == 0) j--;
            System.out.println("i="+i+",j="+j);
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        &#125;
        return nums;
    &#125;

// 作者:jyd
// 链接:https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/mian-shi-ti-21-diao-zheng-shu-zu-shun-xu-shi-qi-4/

&#125;

image.png


好理解,浪费空间

class Solution &#123;
    public int[] exchange(int[] nums) &#123;
        int[] res = new int[nums.length];
        int left = 0;
        int right = nums.length-1;

        int k =0;
        while(k<nums.length)&#123;
            //奇数
            if((nums[k]&1)==1 )&#123;
                res[left++] = nums[k];
            &#125;
            else&#123;
                res[right--] = nums[k];
            &#125;
            k++;
        &#125;
        return res;
    &#125;

&#125;

    public int[] exchange(int[] nums) &#123;
        int p = 0;
        int len = nums.length;
        for(int i = 0; i < len; i ++)&#123;
            if((nums[i]&1)==1)&#123;
                int tmp = nums[i];
                nums[i] = nums[p];
                nums[p++] = tmp;
            &#125;
        &#125;
        return nums;
    &#125;
作者:xmblgt
链接:https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/zhe-dao-ti-you-you-rang-wo-xiang-qi-liao-gczhong-d/

解析
只有遍历到的 nums[i]全为奇数时,p 和 i 保持相同大小,如果遇到偶数元素,那么 i 直接跳过继续 i++,而 p 则会停留在为偶数元素的位置上,这也是为什么要 nums[i]和 nums[p]互换,只有这样才能在一次遍历中把奇数元素位置的元素变为偶数。


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
剑指 Offer 61. 扑克牌中的顺子 剑指 Offer 61. 扑克牌中的顺子
剑指 Offer 61. 扑克牌中的顺子难度简单 98从扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这 5 张牌是不是连续的。2 ~ 10 为数字本身,A 为 1,J 为 11,Q 为 12,K 为 13,而大、小王为 0 ,可以看成任
下一篇 
83. 删除排序链表中的重复元素 83. 删除排序链表中的重复元素
83. 删除排序链表中的重复元素难度简单 480给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例  1:输入: 1->1->2输出: 1->2 示例  2:输入: 1->1->2->3-
2021-03-02 future
  目录