JavaDriver JavaDriver
首页
  • 基础
  • 并发
  • JVM
  • 设计模式
  • 计算机网络
  • 操作系统
  • 数据结构
  • 算法
  • MYSQL
  • REDIS
  • Netty
  • Kafka
系统设计
非技术
关于
  • 分类
  • 标签
  • 归档
GitHub (opens new window)

YoungAnn

西二旗Java老司机一枚 致力于社会主义添砖Java
首页
  • 基础
  • 并发
  • JVM
  • 设计模式
  • 计算机网络
  • 操作系统
  • 数据结构
  • 算法
  • MYSQL
  • REDIS
  • Netty
  • Kafka
系统设计
非技术
关于
  • 分类
  • 标签
  • 归档
GitHub (opens new window)
  • 计算机网络

  • 操作系统

  • 数据结构

  • 算法

  • 剑指Offer题解

    • 数组与矩阵
    • 栈队列堆
    • 双指针
    • 链表
    • 树
    • 贪心
    • 分治
    • 排序
      • 21. 调整数组顺序使奇数位于偶数前面
        • 题目链接
        • 题目描述
        • 解题思路
      • 45. 把数组排成最小的数
        • 题目链接
        • 题目描述
        • 解题思路
    • 动态规划
    • 数学
  • 计算机基础
  • 剑指Offer题解
YoungAnn
2022-10-31
目录

排序

# 21. 调整数组顺序使奇数位于偶数前面

# 题目链接

牛客网(opens new window) (opens new window)

# 题目描述

需要保证奇数和奇数,偶数和偶数之间的相对位置不变,这和书本不太一样。例如对于 [1,2,3,4,5],调整后得到 [1,3,5,2,4],而不能是 {5,1,3,4,2} 这种相对位置改变的结果。

img

# 解题思路

方法一:创建一个新数组,时间复杂度 O(N),空间复杂度 O(N)。

public int[] reOrderArray (int[] nums) {
    // 奇数个数
    int oddCnt = 0;
    for (int x : nums)
        if (!isEven(x))
            oddCnt++;
    int[] copy = nums.clone();
    int i = 0, j = oddCnt;
    for (int num : copy) {
        if (num % 2 == 1)
            nums[i++] = num;
        else
            nums[j++] = num;
    }
    return nums;
}

private boolean isEven(int x) {
    return x % 2 == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 45. 把数组排成最小的数

# 题目链接

牛客网(opens new window) (opens new window)

# 题目描述

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组 {3,32,321},则打印出这三个数字能排成的最小数字为 321323。

# 解题思路

可以看成是一个排序问题,在比较两个字符串 S1 和 S2 的大小时,应该比较的是 S1+S2 和 S2+S1 的大小,如果 S1+S2 < S2+S1,那么应该把 S1 排在前面,否则应该把 S2 排在前面。

public String PrintMinNumber(int[] numbers) {
    if (numbers == null || numbers.length == 0)
        return "";
    int n = numbers.length;
    String[] nums = new String[n];
    for (int i = 0; i < n; i++)
        nums[i] = numbers[i] + "";
    Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
    String ret = "";
    for (String str : nums)
        ret += str;
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
编辑 (opens new window)
上次更新: 2023/02/17, 17:03:51
分治
动态规划

← 分治 动态规划→

最近更新
01
电商-商品系统设计
12-17
02
关于如何写OKR
12-09
03
对事不对人 vs 对人不对事
12-09
更多文章>
Theme by Vdoing | Copyright © 2022-2023 YoungAnnn | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式