SJ Park
BAN USERYou should know the definition of n in time complexity, n is just total number of elements in the algorithm. The time complexity of Merge Sort is known as O(n log n), so this must be at most O(n log n)... N for the size of matrix in the question, it is differ from big O computation... so this is just like O(n log n)..
- SJ Park October 20, 2013I think Merge sort would be good way in the given condition of (array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]).
Implemented in Java with the results.
public class ConvertSorted2Dto1D {
final static int givenN = 5;
private static void merge(int[] lArray, int lLow, int lHi, int[] rArray, int rLo, int rHi, int[] array, int min) {
int[] tempL = new int[lHi - lLow];
int l = 0;
int r = rLo;
int i = min;
System.arraycopy(lArray, lLow, tempL, 0, tempL.length);
// Combine left[] and right[]
while(l < tempL.length && r < rHi) {
if(tempL[l] > rArray[r]) {
array[i++] = rArray[r++];
} else {
array[i++] = tempL[l++];
}
}
// Remaining in left[]
while(l < tempL.length) {
array[i++] = tempL[l++];
}
// Remaining in right[]
while(r < rHi) {
array[i++] = rArray[r++];
}
}
public static void convert2Dto1D(int[][] array2D, int[] array1D) {
for(int i = 1; i < givenN; i++) {
if(i == 1)
merge(array2D[0], 0, givenN, array2D[1], 0, givenN, array1D, 0);
else
merge(array1D, i, i*givenN, array2D[i], 0, givenN, array1D, i);
}
}
public static void main(String[] args) {
int[][] sorted2D = new int[givenN][givenN];
int[] sorted1D = new int[givenN*givenN];
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
sorted2D[i][j] = (int)(Math.random()*9 + i*11 + j*31);
}
}
System.out.println("Before");
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
System.out.print(" " + sorted2D[i][j]);
}
System.out.println();
}
convert2Dto1D(sorted2D, sorted1D);
System.out.println("After");
for(int i = 0; i < givenN * givenN; i++) {
System.out.print(" " + sorted1D[i]);
}
System.out.println();
}
}
Before
5 35 67 100 125
14 49 79 106 139
23 55 89 117 147
40 70 96 130 160
52 79 106 137 175
After
5 14 23 35 40 49 52 55 67 70 79 79 89 96 100 106 106 117 125 130 137 139 147 160 175
It seemed Collection Algorithm could be applicable theoretically, but using this method became more complicated in my case as there were also many internal calculation to be reordered and mapped, so firstly implemented by a general merge method with the results in Java. I only skipped minimum numbers. Can anyone try this by more efficient way of collection algorithm??
Making strategy of partial set of collection was not so difficult, but implementation by a stupid computer was not efficient even though I used iterators of Java, there could be more complicated computation than simple general merge algorithm as I failed...
public class ConvertSorted2Dto1D {
final static int givenN = 5;
private static void merge(int[] lArray, int lL, int lH, int[] rArray, int rL, int rH, int[] array, int min) {
int[] arrayL = new int[lH - lL];
int l = 0;
int r = rL;
int i = min;
System.arraycopy(lArray, lL, arrayL, 0, arrayL.length);
// Combine left[] and right[]
while(l < arrayL.length && r < rH) {
if(arrayL[l] > rArray[r]) {
array[i++] = rArray[r++];
} else {
array[i++] = arrayL[l++];
}
}
// Remaining in left[]
while(l < arrayL.length) {
array[i++] = arrayL[l++];
}
// Remaining in right[]
while(r < rH) {
array[i++] = rArray[r++];
}
}
public static void convert2Dto1D(int[][] array2D, int[] array1D) {
if(givenN > 0) {
System.arraycopy(array2D[0], 0, array1D, 0, givenN);
int min = 1;
for(int i = 1; i < givenN; i++) {
for(; min < i*givenN; min++) {
if(array2D[i][0] < array1D[min]) {
break;
}
}
merge(array1D, min, i*givenN, array2D[i], 0, givenN, array1D, min);
}
}
}
public static void main(String[] args) {
int[][] sorted2D = new int[givenN][givenN];
int[] sorted1D = new int[givenN*givenN];
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
sorted2D[i][j] = (int)(Math.random()*9 + i*11 + j*31);
}
}
System.out.println("Before");
for(int i = 0; i < givenN; i++) {
for(int j = 0; j < givenN; j++) {
System.out.print(" " + sorted2D[i][j]);
}
System.out.println();
}
convert2Dto1D(sorted2D, sorted1D);
System.out.println("After");
for(int i = 0; i < givenN * givenN; i++) {
System.out.print(" " + sorted1D[i]);
}
System.out.println();
}
}
Before
2 39 65 101 125
12 42 74 110 142
26 59 88 122 154
40 72 95 133 161
46 81 107 145 173
After
2 12 26 39 40 42 46 59 65 72 74 81 88 95 101 107 110 122 125 133 142 145 154 161 173
In Java with results according to the instruction.
public class CharacterSequence {
final static int gridWidth = 5;
public static void main(String[] args) {
String[] givenWords = { "CON", "OzOfZo", "xyZoo" };
for(String word : givenWords) {
System.out.println("\nGiven Word : " + word);
findGridSequence(word);
}
}
public static void findGridSequence(String word) {
int curX = 0;
int curY = 0;
for(int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if(ch >= 'a' && ch <= 'z')
ch -= 'a';
else if(ch >= 'A' && ch <= 'Z')
ch -= 'A';
else
continue;
int destX = ch % gridWidth;
int destY = ch / gridWidth;
while(curY != destY || curX != destX) {
while(curX < destX && inRange(findChar(curX+1, curY))) {
curX++;
System.out.println("Right//now at " + findChar(curX, curY));
}
while(curX > destX && inRange(findChar(curX-1, curY))) {
curX--;
System.out.println("Left//now at " + findChar(curX, curY));
}
while(curY < destY && inRange(findChar(curX, curY+1))) {
curY++;
System.out.println("Down//now at " + findChar(curX, curY));
}
while(curY > destY && inRange(findChar(curX, curY-1))) {
curY--;
System.out.println("Up//now at " + findChar(curX, curY));
}
}
System.out.println("OK//to select ---> '" + word.charAt(i) + "'");
}
}
private static boolean inRange(char ch) {
return (ch >= 'A' && ch <= 'Z');
}
private static char findChar(int col, int row) {
return (char)('A' + (row * gridWidth) + col);
}
}
Given Word : CON
Right//now at B
Right//now at C
OK//to select ---> 'C'
Right//now at D
Right//now at E
Down//now at J
Down//now at O
OK//to select ---> 'O'
Left//now at N
OK//to select ---> 'N'
Given Word : OzOfZo
Right//now at B
Right//now at C
Right//now at D
Right//now at E
Down//now at J
Down//now at O
OK//to select ---> 'O'
Left//now at N
Left//now at M
Left//now at L
Left//now at K
Down//now at P
Down//now at U
Down//now at Z
OK//to select ---> 'z'
Up//now at U
Up//now at P
Up//now at K
Right//now at L
Right//now at M
Right//now at N
Right//now at O
OK//to select ---> 'O'
Left//now at N
Left//now at M
Left//now at L
Left//now at K
Up//now at F
OK//to select ---> 'f'
Down//now at K
Down//now at P
Down//now at U
Down//now at Z
OK//to select ---> 'Z'
Up//now at U
Up//now at P
Up//now at K
Right//now at L
Right//now at M
Right//now at N
Right//now at O
OK//to select ---> 'o'
Given Word : xyZoo
Right//now at B
Right//now at C
Right//now at D
Down//now at I
Down//now at N
Down//now at S
Down//now at X
OK//to select ---> 'x'
Right//now at Y
OK//to select ---> 'y'
Left//now at X
Left//now at W
Left//now at V
Left//now at U
Down//now at Z
OK//to select ---> 'Z'
Up//now at U
Up//now at P
Up//now at K
Right//now at L
Right//now at M
Right//now at N
Right//now at O
OK//to select ---> 'o'
OK//to select ---> 'o'
In Java,
public class JavaStringShift {
public static void main(String[] args) {
String str = "abcde";
System.out.println("Input : " + str);
str = strShift(str);
System.out.println("Output : " + str);
}
public static String strShift(String str) {
char[] chars = new char[str.length()];
str.getChars(str.length()-1, str.length(), chars, 0);
str.getChars(0, str.length()-1, chars, 1);
return new String(chars);
}
}
Input : abcde
Output : eabcd
In Java,,,
public class MovieName {
final static int gridWidth = 5;
public static void main(String[] args) {
String[] movie = { "up", "hello", "movie" };
for(String name : movie) {
System.out.println("Input : " + name);
String str = moveGrid(name);
System.out.println("Command : " + str);
str = nameGrid(str);
System.out.println("Output : " + str);
}
}
public static boolean isInRange(int col, int row) {
int ch = 'a' + (row * gridWidth) + col;
return (ch >= 'a' && ch <= 'z');
}
public static String moveGrid(String name) {
StringBuffer sbuf = new StringBuffer();
int curRow = 0;
int curCol = 0;
for(int i = 0; i < name.length(); i++) {
char ch = name.charAt(i);
if(ch < 'a' || ch > 'z')
continue;
ch -= 'a';
int destRow = ch / gridWidth;
int destCol = ch % gridWidth;
while(curRow != destRow || curCol != destCol) {
while(curCol < destCol && isInRange(curCol + 1, curRow)) {
sbuf.append('r');
curCol++;
}
while(curCol > destCol && isInRange(curCol - 1, curRow)) {
sbuf.append('l');
curCol--;
}
while(curRow > destRow && isInRange(curCol, curRow - 1)) {
sbuf.append('u');
curRow--;
}
while(curRow < destRow && isInRange(curCol, curRow + 1)) {
sbuf.append('d');
curRow++;
}
}
sbuf.append('!');
}
return sbuf.toString();
}
public static String nameGrid(String move) {
StringBuffer sbuf = new StringBuffer();
char charIndex = 0;
for(int i = 0; i < move.length(); i++) {
switch(move.charAt(i)) {
case 'l':
charIndex--;
break;
case 'r':
charIndex++;
break;
case 'u':
charIndex -= gridWidth;
break;
case 'd':
charIndex += gridWidth;
break;
case '!':
char ch = (char)('a' + charIndex);
if(ch >= 'a' && ch <= 'z') {
sbuf.append(ch);
}
break;
}
}
return sbuf.toString();
}
}
Input : up
Command : dddd!u!
Output : up
Input : hello
Command : rrd!rru!llldd!!rrr!
Output : hello
Input : movie
Command : rrdd!rr!llldd!rruuu!ru!
Output : movie
My try in Java
public class StrLen {
public static void main(String[] args) {
System.out.println(strlen("abcde"));
}
static int strlen(String str) {
if (str != null) {
for(int len = 0;; len++) {
try {
str.charAt(len);
}
catch (IndexOutOfBoundsException e) {
return len;
}
}
}
return 0;
}
}
In Java for any m*n matrix
public class SpiralMatrix {
public static void main(String[] args) {
Spiral s = new Spiral(5, 5);
s.PrintMatrix();
System.out.println("\nThe output is:\n");
s.PrintSpiral();
System.out.println();
}
}
class Spiral {
int[][] matrix;
Spiral(int m, int n) {
matrix = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
matrix[i][j] = ((i * m) + j + 1) % 10;
}
}
}
public void PrintMatrix() {
for(int i = 0; i < matrix.length; i++) {
System.out.print("[");
for(int j = 0; j < matrix[0].length; j++) {
System.out.print(" " + matrix[i][j]);
}
System.out.println(" ]");
}
}
public void PrintSpiral() {
for(int offset = 0; offset < matrix[0].length - offset; offset++) {
if (offset <= matrix.length / 2)
for(int i = offset; i < matrix[0].length - offset; i++) {
System.out.print(" " + matrix[offset][i]);
}
if (offset <= matrix[0].length / 2)
for(int i = offset + 1; i < matrix.length - offset; i++) {
System.out.print(" " + matrix[i][matrix[0].length - offset - 1]);
}
if (offset < matrix.length / 2)
for(int i = matrix[0].length - offset - 2; i >= offset; i--) {
System.out.print(" " + matrix[matrix.length - offset - 1][i]);
}
if (offset < matrix[0].length / 2)
for(int i = matrix.length - offset - 2; i > offset; i--) {
System.out.print(" " + matrix[i][offset]);
}
}
}
}
[ 1 2 3 4 5 ]
[ 6 7 8 9 0 ]
[ 1 2 3 4 5 ]
[ 6 7 8 9 0 ]
[ 1 2 3 4 5 ]
The output is:
1 2 3 4 5 0 5 0 5 4 3 2 1 6 1 6 7 8 9 4 9 8 7 2 3
Or this in Java depending on the definition of repeating digits.
Output is a little bit different.
public class SkipRepeatingDigits {
public static void main(String[] args) {
NEXT_NUMBER:
for (int i = 45; i <= 4578; i++) {
int previous_digits = -1;
for (int number = i; number != 0; number /= 10) {
if (previous_digits == number % 10) {
continue NEXT_NUMBER;
}
previous_digits = number % 10;
}
System.out.println(i);
}
}
}
Output:
45
46
47
48
49
50
51
52
53
54
56
57
58
59
60
61
62
63
64
65
67
68
69
70
71
72
73
74
75
76
78
79
80
81
82
83
84
85
86
87
89
90
91
92
93
94
95
96
97
98
101
102
103
104
105
106
107
108
109
120
121
123
124
125
126
127
128
129
130
131
132
134
135
136
137
138
139
140
How abut this in Java as it should be O(n) complexity.
public class FindStartEndNumberIndex {
public static void main(String[] args) {
int[] Array = { 0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9 };
findIndex(Array, 3);
findIndex(Array, 5);
}
static void findIndex(int[] array, int number) {
int startIndex = -1, endIndex = -1;
for(int i = 0; i < array.length; i++) {
if(array[i] == number) {
if(startIndex < 0) {
startIndex = i;
}
endIndex = i;
}
}
System.out.printf("{%d,%d}\n", startIndex, endIndex);
}
}
Output:
{3,6}
{-1,-1}
How about this in Java?
public class SkipRepeatingDigits {
public static void main(String[] args) {
NEXT_NUMBER:
for (int i = 45; i <= 4578; i++) {
boolean[] digits = new boolean[10];
for (int number = i; number != 0; number /= 10) {
if (digits[number % 10]) {
continue NEXT_NUMBER;
}
digits[number % 10] = true;
}
System.out.println(i);
}
}
}
Output:
45
46
47
48
49
50
51
52
53
54
56
57
58
59
60
61
62
63
64
65
67
68
69
70
71
72
73
74
75
76
78
79
80
81
82
83
84
85
86
87
89
90
91
92
93
94
95
96
97
98
102
103
104
105
106
107
108
109
120
123
124
125
126
127
128
129
130
132
134
The definition of n in the time complexity, this is just total number of elements, so I must agree with Michael J Keating who gave us the most closed answer.
- SJ Park October 20, 2013Merge Sort is just known as O(n log n), and the time complexity of his algorithm is less than Merge Soft big O analysis. The N for the 2D matrix in the question is differ from n in the time complexity computation as it is just total number of elements.. don't be confused if I am right...