IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 剑指offer - 调整数组顺序使奇数位于偶数前面 -> 正文阅读

[数据结构与算法]剑指offer - 调整数组顺序使奇数位于偶数前面

题目描述

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

示例

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

算法思路

思路一

采用左右双指针的技巧:

  1. 定义左指针left,右指针right
  2. 左指针一直往右移,直到所指的数是偶数
  3. 右指针一直往左移,直到所指的数是奇数
  4. 交换nums[left]和nums[right]
  5. 直到 left == right 为止

思路二

采用快慢双指针的技巧

  1. 定义low = fast = 0
  2. fast 一直向前搜索奇数的位置,low则是下一个奇数要存放的位置。
  3. 当 fast 搜索到奇数时,交换和 low 的位置,low++
  4. 直到 fast 指向数组末尾

代码实现

实现一

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            //如果是奇数,一直往右移
            if((nums[left]&1)==1){
                left++;
                continue;
            }
            //如果是偶数,一直往左移
            if((nums[right]&1)==0){
                right--;
                continue;
            }
            //左指针碰到偶数,右指针碰到奇数,交换
            swap(nums,left++,right--);
        }
        return nums;
    }

    private void swap(int[]nums,int a,int b){
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}

实现二

class Solution {
    public int[] exchange(int[] nums) {
        int low = 0;
        int fast = 0;
        while(fast<nums.length){
            //如果快指针所指的是奇数,交换和low所指的位置
            if((nums[fast]&1)==1){
                swap(nums,low,fast);
                low++;
            }
            //fast一直向前搜索,碰到奇数就交换
            fast++;
        }
        return nums;

    }

    private void swap(int[]array,int a,int b){
        int c = array[a];
        array[a] = array[b];
        array[b] = c;
    }
}

题目改进

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

示例

输入:[2,4,6,5,7]
返回值:[5,7,2,4,6]
注:[7,5,6,4,2]不是正确答案

题目这样一改就不能使用双指针了,因为使用双指针的话,他们的相对位置就会改变

我这里采用的思路是:

  1. 使用两个存储结构,一个存储奇数,一个存储偶数
  2. 指针向前移动,碰到奇数,就把奇数存储到奇数的数据结构里,碰到偶数就存储到偶数的数据结构里
  3. 最后把偶数的数据结构拼接到奇数的数据结构里

代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        int[] odd = new int[array.length];
        ArrayList<Integer> even = new ArrayList<>();
        int j = 0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0){
                even.add(array[i]);
            }else{
                odd[j] = array[i];
                j++;
            }
        }
        
        for(int i=0;i<even.size();i++){
            odd[j] = even.get(i);
            j++;
        }
        
        return odd;
    }
}
  数据结构与算法 最新文章
【数据结构】第二章线性表:双链表、静态链
A + B Problem c++ 题解
剑指 Offer 25. 合并两个排序的链表(双指针
数字存储示波器数字荧光算法
Leetcode 102.二叉树的层序遍历
排序算法介绍及学习卡壳点理解
leetcode-123. 买卖股票的最佳时机 III
01背包的朴素解法及优化(C语言)
用链表实现的队列
数组形式的整数加法
上一篇文章      下一篇文章      查看所有文章
加:2021-07-16 11:33:17  更:2021-07-16 11:35:23 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年10日历 -2021/10/28 11:49:19-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码