java - 创建一个列表，其中包含 2 个对象，其中第一个在升序中，另一个在降序中合并为一个

Question

根据以下内容对列表进行排序: 一个列表按升序排列，另一个列表按降序排列，然后在保持顺序的情况下合并为一个列表。

有 2 个列表 A 和 B，附有如下数字:

Eg: 
A1  B2
A2  B3
A6  B4
A7  B8
A10 B9

排序顺序为:

A1
A2
B4
B3
B2
A6
A7
B9
B8
A10

任何建议都会有帮助

编辑 我使用 @karzler007 建议的算法在 Java 中制作了程序

import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void main(String[] args) {

        List<Integer> a = new ArrayList<Integer>();
        List<Integer> b = new ArrayList<Integer>();

        a.add(1);
        a.add(2);
        a.add(6);
        a.add(7);
        a.add(10);

        b.add(2);
        b.add(3);
        b.add(4);
        b.add(8);
        b.add(9);

        int i = a.size() - 1;
        int j = b.size() - 1;

        int k = a.size() + b.size() - 1;
        List<Integer> ans = new ArrayList<Integer>();
        for (int h = 0; h < k + 1; h++) {
            ans.add(0);
        }

        while (k >= 0) {
            if (j < 0) {
                while (i >= 0) {
                    ans.set(k--, a.get(i--));
                }
            } else if (i < 0) {
                int l = 0;
                while (l <= j) {
                    ans.set(k--, b.get(l++));
                }
            } else {
                while (a.get(i) >= b.get(j)) {
                    ans.set(k--, a.get(i--));
                }
                int m = j;
                int n = j;
                while (j >= 0 && b.get(j) >= a.get(i)) {
                    j--;
                }
                m = j + 1;
                for (int e = m; e <= n; e++) {
                    ans.set(k--, b.get(e));
                }
            }
        }
        System.out.println(ans);
    }
}

欢迎提出任何改进代码的建议。

Answer 1

您正在查看的是归并排序的修改版本。您现在可以考虑一个数组以非递减顺序排列，另一个数组以非递增顺序排列，而不是以非递减或非递增方式排序的两个数组。以下代码片段执行修改后的合并步骤。

// a is in non-decreasing order, b is in non-increasing order.

public static int[] merge(int[] a, int[] b) {
    int[] ans = new int[a.length + b.length];
    int i = a.length - 1, j = 0, k = ans.length;

    while (k > 0)
        ans[--k] = 
            (j > b.length-1 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j++];
    return ans;
 }

编辑:抱歉，我对问题的理解有误。请在下面找到算法的更正版本。

    int a[] = {1, 2, 6, 7, 10};
    int b[] = {2, 3, 4, 8, 9};
    int[] ans = new int[a.length + b.length];
    int i = a.length - 1;
    int j = b.length - 1;
    int k = a.length + b.length - 1;
    while (k >= 0) {
        if (j < 0) {
            while (i >= 0) {
                ans[k--] = a[i--];
            }
        } else if (i < 0) {
            int l = 0;
            while (l <= j) {
                ans[k--] = b[l++];
            }
        } else {
            while (a[i] >= b[j]) {
                ans[k--] = a[i--];
            }
            int m = j;
            int n = j;
            while (j >= 0 && b[j] >= a[i]) {
                j--;
            }
            m = j + 1;
            for (int e = m; e <= n; e++) {
                ans[k--] = b[e];
            }
        }
    }
    System.out.println(Arrays.toString(ans));

上述算法确实为您提供了所需的输出:

   [1, 2, 4, 3, 2, 6, 7, 9, 8, 10]

希望对你有帮助。