检测一个字符串是否可以只通过一次两个elements的交换实现排序!


Check if the array can be sorted with a single swap of 2 elements

write a function that will check if the array can be sorted with a single swap of the values in the array.

For example: array(1,3,5,3,7) must return true,

but array(1,3,5,3,4) must return false.

我先小TRY一把:
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

int solution(int A[], int N) {
    int inv_count = 0;
    int i, j;
    for (i = 0; i < N - 1; i++)
    for (j = i + 1; j < N; j++)
    if (A[i] > A[j])
        inv_count++;

    if (inv_count<2)
        return 1;
    else
        return 0;
}
已邀请:

cpcs - 诚实努力

赞同来自: 邹博 simbest 段さん ywhu


再优化一点 : 时间复杂度O(N), 空间复杂度O(1)
基本观点 ....i.....j.... (i,j) 是交换过的两个位置, 那么必须a[i] > a[i + 1]并且 a[j]是i + 1以后面最小的值。
所以我们先找到这样的i和j,然后交换回来,看看是否是有序的。
注意我们只找了一个这样的i,然后找j,然后交换,然后判断,整个是线性的。
如果找不到这样的i,那么扫一遍之后就直接return true了。
if (N <= 0) {
    return true;
}
for (int i = 0; i + 1 < N; ++i) {
    if (a[i] > a[i + 1]) { // i是一个不合法的位置 我们找到后面最小的位置
        j = i + 1;
        for (int k = j; k < N; ++k) {
            if (a[k] < a[j]) {
                j = k;
            }
        }
        // j是i后面最小值的位置
        swap(a[i], a[j]);
        for (int k = i; k + 1 < N; ++k) {  //看一下交换后面是不是有序的
            if (a[k] > a[k + 1]) {
                return false;
            }
        }
        return true;
    }
}
return true;

要回复问题请先登录注册