1. 有一个数组，按偶奇降序排序后，按照偶奇的形式交替输出，例如{2, 4, 3, 6, 1, 5, 7, 8, 9}，则输出结果为{8, 9, 7, 4, 5, 2, 3, 1}
解题思路：
先按照最简单的办法：先把数组分成奇偶两个数组，再对这两个数组进行降序排序，最后再交替输出。
代码：
public class Test1 {
public static void main(String[] args) {
int[] arr = { 2, 4, 6, 1, 5, 7, 8, 9 };
System.out.println(evenOddSort(arr));
}
public static String evenOddSort(int[] nums) {
int length = nums.length;
List<Integer> evenList = new ArrayList<Integer>();
List<Integer> oddList = new ArrayList<Integer>();
for (int i = 0; i < length; i++) {
int num = nums[i];
if (num % 2 == 0) {
evenList.add(num);
} else {
oddList.add(num);
}
}
// 降序排序
sortDesc(evenList);
sortDesc(oddList);
// 公共的次数
int time = evenList.size() > oddList.size() ? evenList.size() : oddList.size();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < time; i++) {
list.add(evenList.get(i));
list.add(oddList.get(i));
}
// 剩余的次数
if (evenList.size() > oddList.size()) {
for (int i = time; i < evenList.size(); i++) {
list.add(evenList.get(i));
}
}else {
for (int i = time; i < oddList.size(); i++) {
list.add(oddList.get(i));
}
}
return list.toString();
}
public static void sortDesc(List<Integer> list) {
for (int i = 0; i < list.size(); i++) {
for (int j = 0; j < list.size() - i - 1; j++) {
int current = list.get(j);
int next = list.get(j + 1);
if (current < next) {
list.set(j + 1, current);
list.set(j, next);
}
}
}
System.out.println(list);
}
}
虽然解决了这个问题，但是代码很复杂，在室友的启发下，有了一种新的思路：先把列表进行降序排序，然后再用两个索引（或者叫指针），分别代表下一个偶数位置和奇数位置，使用List<Integer>来存储要输出的数组，这样在每次遍历只需要分别放入一个偶数和奇数即可。
代码：
public class Test1pro {
public static void main(String[] args) {
int[] arr = { 2, 4, 6, 1, 5, 7, 8, 9 };
System.out.println(evenOddSort(arr));
}
public static String evenOddSort(int[] nums) {
int length = nums.length;
// 降序排序
for (int i = 0; i < length; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (nums[j] < nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(nums));
int even = 0, odd = 0;
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < length; i++) {
// 用两个索引表示偶奇数的位置
// 下一个偶数
while (even < length && nums[even] % 2 != 0) {
even ++;
}
if (even < length) {
list.add(nums[even]);
even ++;
}
// 下一个奇数
while (odd < length && nums[odd] % 2 == 0) {
odd ++;
}
if (odd < length) {
list.add(nums[odd]);
odd ++;
}
}
return list.toString();
}
}
2. 有一个数组，求输出能够组成的最大数，例如{20, 13, 9, 6}，则输出结果为962013
解题思路：
针对给出的示例数组，按照正常的思维，那么只需要取出每个首位比较大小即可。但是如果存在首位相同的情况，那么就需要继续判断；例如{20, 211}，解决办法就是设较小数的长度为x，那么只需要取两个数的前x位比较大小即可；但是如果两个数的前x位大小也一样呢？比如{20, 201}，那么我们还要把较大数截掉前x位后剩下的数的首位和前x位的数的首位进行比较。可能听起来很拗口，我举个例子：
例如数组{20, 201}，较小数为20，长度为2，这两个数的前2位都是20，则较大数201截掉前前2位后还剩下一个1，那么这个1比2小，所以组成的数是20201，但是如果是{20, 205}，那么剩下的5就要比2大，则组成的数应该是20520。
代码：
public class Test2 {
public static void main(String[] args) {
// [13, 6, 9]
// [21, 2, 1]
// [20, 1, 205]
// [9, 7, 979, 997, 799] 9 997 979 799 7
int[] nums = {9, 7, 979, 997, 799};
System.out.println(maxNum(nums));
}
public static String maxNum(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
compare(i, j, nums);
}
}
StringBuffer buffer = new StringBuffer();
for (int num : nums) {
buffer.append(num);
}
return buffer.toString();
}
public static void compare(int i, int j, int[] nums) {
int current = nums[i];
int next = nums[j];
System.out.println(current + " " + next + "数组：" + Arrays.toString(nums));
int clength = String.valueOf(current).length();
int nlength = String.valueOf(next).length();
if (clength != nlength) {
// 最短长度
int min = clength < nlength ? clength : nlength;
// 把两个数转成字符串
String cstr = String.valueOf(current);
String nstr = String.valueOf(next);
// 按照最短长度进行裁剪
// 并转化为整型进行大小比较
int minCurrent = Integer.parseInt(cstr.substring(0, min));
int minNext = Integer.parseInt(nstr.substring(0, min));
if (minCurrent == minNext) {
// 代表前面公共部分是相同的
// 但是并不代表数长的肯定比数短的小
// 还需要进一步判断
// 比如【21, 2】和【20， 205】
// 取出相同部分的首位
int first = Integer.parseInt(cstr.substring(0, 1));
if (clength > nlength) {
// 剩余的部分的首位
int last = Integer.parseInt(cstr.substring(min, min + 1));
// 如果剩余的部分的首位比相同部分的首位小
// 则需要对调两个数
if (last < first) {
nums[i] = next;
nums[j] = current;
}
} else {
// 多余的部分
int last = Integer.parseInt(nstr.substring(min, min + 1));
// 如果剩余的部分的首位比相同部分的首位大
// 则需要对调两个数
if (last > first) {
nums[i] = next;
nums[j] = current;
}
}
} else {
// 虽然长度不一样
// 但是只需要比较相同的长度的数的大小即可
if (minCurrent < minNext) {
nums[i] = next;
nums[j] = current;
}
}
} else {
// 代表两个数长度一样
// 那么只需要比较两个数的大小即可
if (current < next) {
nums[i] = next;
nums[j] = current;
}
}
}
}
后续可能还会更新~
网友评论