Problem:
Find two swapped elements in an almost sorted array.For example
given array [1,4,3,2,5,6]
the answer is:
4 and 2
Solution:
this is a classical problem that can be achieved with one pass and no extra space.
class Solution {
public static void main(String...args) {
int[] a = new int[]{1,4,3,2,5,6};
int x = -1;
int y = -1;
for(int i = 0; i < a.length - 1; i++) {
if(a[i] > a[i+1]) {
y = a[i + 1];
if(x == -1) x = a[i];
else break;
}
}
System.out.println(x + "," + y);
}
}
public static void main(String...args) {
int[] a = new int[]{1,4,3,2,5,6};
int x = -1;
int y = -1;
for(int i = 0; i < a.length - 1; i++) {
if(a[i] > a[i+1]) {
y = a[i + 1];
if(x == -1) x = a[i];
else break;
}
}
System.out.println(x + "," + y);
}
}
Time complexity O(N), space complexity O(1).
This is a simple problem, but the same principle can be used to solve harder problems such as recover binary search tree.
This is a simple problem, but the same principle can be used to solve harder problems such as recover binary search tree.
