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

野性酷女 2022-09-10 06:15 34阅读 0赞

> 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
> 
> 示例：
> 
> 输入：nums = \[1,2,3,4\]  
> 输出：\[1,3,2,4\]  
> 注：\[3,1,2,4\] 也是正确的答案之一。  
> 
> 
> 提示：
> 
> 0 <= nums.length <= 50000  
> 1 <= nums\[i\] <= 10000
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

奇数位于前半部分，偶数位于后半部分，可以采用首尾双指针法。类似于快排的方法

public int[] exchange(int[] nums) {
            int i = 0,j = nums.length - 1,tmp;
            while(i < j){
                while(i < j && nums[i] % 2 != 0){ i++; }
                while(i < j && nums[j] % 2 == 0){ j--; }
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
            return nums;
        }

改进一下这个算法：

public int[] exchange1(int[] nums) {
            int i = 0,j = nums.length - 1,tmp;
            while(i < j){
                // &表示位运算，位运算的效率比取余或者乘除运算效率更高，而且考虑到正负奇偶数的情况，用&更合适
                while(i < j && (nums[i] & 1) == 0 ){ i++; }
                while(i < j && (nums[j] & 1) == 0){ j--; }
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                //减少了再次回到上面进行重复while判断的次数，既然已经交换了，
                //那么i与j位置的奇偶已经分明，所以只需要去判断下一位即可
                i++;
                j--;
            }
            return nums;
        }

另一种方法，快慢双指针法，只需要一个循环就可以了，这个方法也可以用来调整单链表而不用知道链表的长度。

public int[] exchange2(int[] nums) {
            int slow = 0,fast = 0,tmp;
            while(fast < nums.length){
                if((nums[fast] & 1) == 0){
                    tmp = nums[slow];
                    nums[slow] = nums[fast];
                    nums[fast] = tmp;
                    slow++;
                }
                fast++;
            }
            return nums;
        }

--------------------

有时候我们会有一种感觉，在做事情的时候，会想着怎么样去玩，在玩的时候，会想起来还有什么任务没有完成。这样就会导致玩也没玩好，工作也没工作好。

这就需要我们转变一下思路，划分工作学习与放松娱乐的界限。

划分出某个时间段为学习时间，在这个时间段里，你可以学习，也可以不学习。但是过了这个时间段，就一定不能学习，必须去放松娱乐。有了一定的紧迫感，有了工作学习与放松娱乐的界限感，两者都会更加纯粹，更能提高效率。