learn-to-code
Given a string which contains only letters. Sort it by lower case first and upper case second. Example: For “abAcD”, a reasonable answer is “acbAD”. Challenge: You should do it in one-pass and in-place.
C++ Solution
No additional space should be used. We can use two pointers to skip in-place characters from both end, swap them if they are not until they meet in the middle.
The space complexity is O(1) and the time complexity is O(n).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: /* * @param chars: The letter array you should sort by Case * @return: nothing */ void sortLetters(string &chars) { int i = 0, j = chars.length() - 1; while (i <= j) { // skipping in-place lower characters from the begining while ((chars[i] >= 'a') && (chars[i] <= 'z') && i < j) i ++; // skipping in-place upper characters from the end while ((chars[j] >= 'A') && (chars[j] <= 'Z') && i < j) j --; // swap auto t = chars[i]; chars[i] = chars[j]; chars[j] = t; i ++; j --; } } }; |
class Solution {
public:
/*
* @param chars: The letter array you should sort by Case
* @return: nothing
*/
void sortLetters(string &chars) {
int i = 0, j = chars.length() - 1;
while (i <= j) {
// skipping in-place lower characters from the begining
while ((chars[i] >= 'a') && (chars[i] <= 'z') && i < j) i ++;
// skipping in-place upper characters from the end
while ((chars[j] >= 'A') && (chars[j] <= 'Z') && i < j) j --;
// swap
auto t = chars[i];
chars[i] = chars[j];
chars[j] = t;
i ++;
j --;
}
}
};–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
248 wordsloading...
Last Post: The Colour Chart Generator in C++
Next Post: C++ Coding Exercise - Search Insert Position
