java – 如何知道一个数组是否可以按一个或多个交换排序?

前端之家收集整理的这篇文章主要介绍了java – 如何知道一个数组是否可以按一个或多个交换排序?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一个包含n个元素的数组,我们可以通过执行一个交换操作来按升序对这个数组进行排序吗?

例如下面的数组:

int[] data = {1,9,6,3}

我们只需要用9进行交换,只有一个交换操作,我的数组可以按照升序排列.如果数组已经按升序排序,那么我们可以直接返回true.

我开始下面的代码,但我被卡住了,我不知道我该怎么办?

public static boolean verifyOrder(int[] data) {
    List<Integer> input = new ArrayList<Integer>();
    for (int index = 0; index < data.length; index++) {
        input.add(data[index]);
    }
    int j = 0;
    while (j < input.size() - 1 && input.get(j) <= input.get(j + 1)) {
        j++;
    }
    if (j == input.size() - 1) {
        // yes we can sort array with only one swap operation
        return true;
    }

    // not sure how should I proceed?
}

处理这个问题的有效方式是什么?

解决方法

我会给你一些提示

>您必须对数组进行一次迭代,以验证其已经被排序(即,将每个i的数据[i] i = i [i i]从0变为数据长度2).
>如果在这个单独的迭代中,你会发现数据[i]>数据[i 1]对于某些我,你知道数据[i]在错误的地方.如果可以做一个单一的交换,使数组排序,你需要交换数据[i]的东西.为了找到哪个元素与数据[i]进行交换,搜索最小的数据[j],其中j> i.在使用数据[j]交换数据[i]之后,您可以在数组上重复一次以验证它是否被排序.

最多你会在数组上迭代两次,这将给你O(n)运行时间.

原文链接:https://www.f2er.com/java/123942.html

猜你在找的Java相关文章