Как узнать, можно ли отсортировать массив по одному свопу или меньше?
Учитывая массив с n элементами, можем ли мы отсортировать этот массив в порядке возрастания, выполнив только одну операцию свопинга?
Например, для следующего массива:
int[] data = {1 , 9 , 6, 3}
Нам нужно поменять местами только 9 на 3 и что только одна операция смены, по которой мой массив может быть в порядке возрастания. Если массив уже отсортирован в порядке возрастания, мы можем напрямую вернуть 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?
}
Каков эффективный способ решения этой проблемы?
Ответы
Ответ 1
Я дам вам несколько советов:
-
Вам нужно перебирать массив точно один раз, чтобы проверить, что он уже упорядочен (т.е. проверьте, что data[i]<=data[i+1] для каждого i от 0 до data.length-2).
-
Если во время этой единственной итерации вы обнаружите, что data[i]>data[i+1] для некоторого i, вы знаете, что data[i] находится не в том месте. Если возможно сделать один обмен, который заставит массив упорядочить, вам нужно сменить data[i] на что-то. Чтобы найти какой элемент для обмена data[i] с, найдите самый маленький data[j], где j>i. После замены data[i] на data[j] вы можете повторить еще раз по массиву, чтобы убедиться, что он упорядочен.
В лучшем случае вы будете перебирать два раза по массиву, что даст вам время O(n).
Ответ 2
O(nlogn).: (
Ответ 3
Возможно, это будет выглядеть так:
public static boolean CheckSingleSwap(int[] A)
{
int count = 0;
int[]B = Arrays.copyOf(A, A.length);
Arrays.sort(B);
for(int i=0; i<A.length; i++)
{
if(A[i] != B[i]) count++;
}
if(count > 2) return false;
return true;
}
Я тестировал, что используя ниже массивы:
int[]A = {1,2};
int[]B = {1,3,6,3,5,5,3,7,7};
int[]C = {1, 4, 5, 6, 7, 2};
int[]D = {1,2,3,4,5,6,7,8,9,10,11,2,45,56,67,78,89,90,123,124,1245566778};
int[]D1 = {1,2,3,4,5,6,7,8,9,10,11,2,45,56,67,78,89,90,2,123,124,1245566778};
int[]E = {1, 5, 3, 3, 7} ;
int[]F= {1, 3, 5};
int[]G = {1,5,3};
System.out.println("A : "+CheckSingleSwap(A));
System.out.println("B : "+CheckSingleSwap(B));
System.out.println("C : "+CheckSingleSwap(C));
System.out.println("D : "+CheckSingleSwap(D));
System.out.println("D1 : "+CheckSingleSwap(D1));
System.out.println("E : "+CheckSingleSwap(E));
System.out.println("F : "+CheckSingleSwap(F));
И результат:
A : true
B : true
C : false
D : false
D1 : false
E : true
F : true
Mmmm... Скажите, если что-то не так с CheckSingleWap()...: D
Спасибо..
Ответ 4
Я думаю, что этот код будет работать
public class Test2 {
public static void main(String[] args) throws Exception {
int arr[] = {3,3,4,6,7,8,9,11,10};
Test2 test = new Test2();
System.out.println(test.swapSorting(arr));
}
public boolean isSorted( int arr[]) {
boolean flag = false;
for(int i=0; i<arr.length ; i++) {
if(i+1 < arr.length) {
if(arr[i] <= arr[i+1]) {
flag = true;
} else {
flag = false;
break;
}
}
}
return flag;
}
public boolean swapSorting(int arr[]) {
boolean flag = false;
if(isSorted(arr)) {
return true;
} else {
for(int i=0; i<arr.length ; i++) {
for(int j=1; j<arr.length ; j++) {
int arr1[] = Arrays.copyOf(arr, arr.length);
int temp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = temp;
if(isSorted(arr1)) {
flag = true;
break;
}
}
}
}
return flag;
}
}
Ответ 5
Следующее должно работать для вас...
private boolean function(int[] data) {
int max = data[0], maxIndex = 0;
//find the maximum element in the array
for(int i=0;i<data.length;i++)
{
if(data[i] > max)
{
max = data[i];
maxIndex = i;
}
}
//check whether all the elements before max are less than it
// if not you need more swaps to sort
for(int j=0;j<maxIndex;j++)
{
if(data[j]>max)
return false;
}
//check what is next smallest element
for(int j=maxIndex+1;j<data.length-1;j++)
{
if(!(max > data[j] && data[j+1] <data[j]))
return false;
}
return true;
}
Сообщите мне, требуется ли дополнительная информация
Ответ 6
Простое и точное решение
public boolean checkSortedArray(int[] arr){
if(arr==null)
return false;
boolean flag=true;
for(int i=0;i<arr.length-1;i++){
if(arr[i]>arr[i+1]){
if(flag)
return false;
int j=i+2;
while(j<arr.length && arr[j]>=arr[i+1])
j++;
if(j>=arr.length)
return false;
swap(arr, i, j);
flag=true;
}
}
return true;
}
Ответ 7
package CodingPratise;
public class SingleSwapSorting {
public static void main(String [] args){
int [] a = {1,4,5,6,7,2};
int count =0; int index = 0; int minValue = 0; int maxValue =a[0];int indexMax = 0; int flag = 0;
for (int i = 0; i < (a.length-1); ++i){
/*find the min number and its index, as long as min is occured in the loop only twice. */
if ((a[i] > a[i+1]) && count <= 2) {
count ++;
index = i+1;
minValue = a[i+1];
flag = 1;
}
else {
continue;
}
}
if(count <= 2 && flag == 1){
/*Now find the max from the loop so iterate one more time and swap the values. */
for(int i = 0; i < (a.length-1); i++){
if ((a[i] > maxValue)) {
indexMax = i;
maxValue = a[i];
int temp = a[indexMax];
a[indexMax] = a[index];
a[index] = temp;
}
}
}
for(int b:a){
System.out.println(b);
}
}}
Ответ 8
Код Python для вашей справки. Он протестирован для большинства примеров, опубликованных здесь.:
def solution(A):
n=len(A)
if n==1:
return True
h=0
for i in xrange(1,n):
if A[i]<A[i-1]:
break
elif A[i]>A[i-1]:
h=i
if i==n-1:
return True
k = n-1
for j in xrange(n-1, 0, -1):
if A[j-1]>A[j]:
break
elif A[j-1]<A[j]:
k=j-1
temp=A[k]
A[k]=A[h]
A[h]=temp
for i in xrange(len(A) - 1):
if A[i] > A[i + 1]:
return False
return True
Ответ 9
этот код написан быстрым, любой хочет преобразовать его в java? В основном вдохновленный решением @Eran, просто изменил его немного, чтобы поймать несколько неудавшихся случаев.
func singleSwap(_ arr: [Int]) -> Bool {
let count = arr.count;
var sorted = true;
var unsortedStartIndex = -1;
for index in 0...count-2 {
if (arr[index] <= arr[index + 1]) {
continue;
} else {
unsortedStartIndex = index;
sorted = false;
break;
}
}
guard !sorted else {
return true;
}
var result = false;
let newStartIndex = unsortedStartIndex + 1;
for index in newStartIndex...count-2 {
if (arr[index] >= arr[index+1]) {
continue;
} else {
if (arr[unsortedStartIndex] >= arr[index] && arr[unsortedStartIndex] <= arr[index+1]) {
result = true;
break;
}
}
}
return result;
}
Ответ 10
static boolean isSingleSwapSort(int a[]) {
int cnt = 0;
for (int i = a.length - 1; i > 0; i--) {
if (cnt > 1) {
return false;
}
if (a[i] < a[i - 1]) {
int j = i - 1;
while (j >= 0 && a[i] <= a[j]) {
j--;
if (a[j] > a[j + 1]) {
j--;
break;
}
}
j++;
int t = a[i];
a[i] = a[j];
a[j] = t;
cnt++;
i++;
}
}
return true;
}
public static void main(String arg[]) {
int[] A = { 1, 2 };
int[] B = { 1, 3, 6, 3, 5, 5, 3, 7, 7 };
int[] C = { 1, 4, 5, 6, 7, 2 };
int[] D = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2, 45, 56, 67, 78, 89,
90, 123, 124, 1245566778 };
int[] D1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2, 45, 56, 67, 78, 89,
90, 2, 123, 124, 1245566778 };
int[] E = { 1, 5, 3, 3, 7 };
int[] F = { 1, 3, 5 };
int[] G = { 1, 5, 3 };
System.out.println("A:" + isSingleSwapSort(A));
System.out.println("B:" + isSingleSwapSort(B));
System.out.println("C:" + isSingleSwapSort(C));
System.out.println("D:" + isSingleSwapSort(D));
System.out.println("D1:" + isSingleSwapSort(D1));
System.out.println("E:" + isSingleSwapSort(E));
System.out.println("F:" + isSingleSwapSort(F));
System.out.println("G:" + isSingleSwapSort(G));
}
