xuzheng712
BAN USERO(N) time
1: /**
2: *
3: * @param S
4: * @param K the number of characters to remove
5: * @return
6: */
7: public String generateLowestNumber(String S, int K) {
8: if (S == null || K > S.length()) {
9: return "";
10: }
11: // removing K digits is the same as keeping N - K digits
12: int add = S.length() - K; // the number of characters to add.
13: char[] lowest = new char[add];
14: // convert the input into an array of digits
15: int[] digits = new int[S.length()];
16: for (int i = 0; i < digits.length; i++) {
17: digits[i] = S.charAt(i) - '0';
18: }
19: int index = 0;
20: int[] closest = new int[S.length()];
21: closest[digits.length - 1] = -1;
22: for (int i = digits.length - 2; i >= 0; i--) {
23: int j = i + 1;
24: while (j != -1 && digits[i] <= digits[j]) {
25: j = closest[j];
26: }
27: closest[i] = j;
28: }
29: for (int i = 0; i < add; i++) {
30: int j = index;
31: while (j != -1 && j <= (digits.length - (add - i))) {
32: lowest[i] = (char) (digits[j] + (int) '0');
33: index = j;
34: j = closest[j];
35: }
36: index++;
37: }
38: return String.valueOf(lowest);
39: }
public static int maxPairs(char[] A) {
if(A==null) {
return 0;
}
int count = 0;
Stack<Character> st = new Stack<Character>();
for (int i = 0; i < A.length; i++) {
if(st.isEmpty()) {
st.push(A[i]);
} else if(st.peek()==A[i]) {
count++;
st.pop();
} else {
st.push(A[i]);
}
}
return count;
}
Your solution is the same as my solution. I think it works well, but you forgot to print out the number of occurrences of the elements that do appear in the input array.
- xuzheng712 August 08, 2013The range 1 to n is a restriction on the input array, however this does not mean we can't change elements in the input array to an integer that is outside the range.
Of course, this solution only works if I can make the assumption that the input is an array of signed integers.
My solution changes the input array. I did not use an extra array, so the amount of extra memory is constant.
- xuzheng712 July 31, 2013My solution is O(n) time and O(1) space. I did not sort the array.
- xuzheng712 July 31, 2013public static void elements(int[] A) {
for (int i = 0; i < A.length; i++) {
while (A[i] != i + 1) {
int temp = A[A[i] - 1];
if (temp == A[i]) {
break;
}
A[A[i] - 1] = A[i];
A[i] = temp;
}
}
System.out.println("Elements that don't exist in array A");
for (int i = 0; i < A.length; i++) {
if (A[i] != i + 1) {
System.out.println(i + 1);
} else {
A[i] = -1;
}
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0) {
A[A[i] - 1]--;
}
}
System.out.println("Elements that exist in array A and their frequency");
for (int i = 0; i < A.length; i++) {
if (A[i] < 0) {
System.out.println((i + 1) + ": " + (-A[i]));
}
}
}
public static void main(String[] args) {
// TODO code application logic here
int[] A = {9,9,9,9,9,9,9,8,7,9,10};
elements(A);
}
Result:
Elements that don't exist in array A
1
2
3
4
5
6
11
Elements that exist in array A and their frequency
7: 1
8: 1
9: 8
10: 1
zhengxucoding.wordpress.com/2015/04/19/minimum-number-formed-by-deleting-k-digits/
- xuzheng712 April 20, 2015