# [NineChap 2.2] Sorted Array

## Sorted Array

#### Template

There is no template.

#### Question list

1. Reverse Words in a String

2. Rotate String

Given string “abcdefg” and offset = 3, the rotated string is “efgabcd”.

## Code

Remove Duplicates from Sorted Array

``````public int removeDuplicates(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int left = 1;
int right = 1;
while (right < A.length) {
if (A[right - 1] != A[right]) {
A[left] = A[right];
left++;
}
right++;
}
return left;
}
``````

Remove Duplicates from Sorted Array II - slightly difficult in coding

``````public int removeDuplicates(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int left = 1;
int right = 1;
boolean twice = false;
while (right < A.length) {
if (A[right - 1] != A[right]) {
A[left++] = A[right++];
twice = false;
} else if (!twice){
A[left++] = A[right++];
twice = true;
} else {
right++;
}
}
return left;
}
``````

Merge Sorted Array

Easy question, tail to head merge.

Median of Two Sorted Arrays

This question is Find kth largest from A&B. Refer to original post.

Recover Rotated Sorted Array

I wrote a new post.

Reverse Words in a String

``````public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return s;
}
String[] words = s.split(" ");
String firstReversed = "";
for (int i = 0; i < words.length; i ++) {
if (words[i].equals("")) continue;
firstReversed += inPlaceReverse(words[i]) + " ";
}
return inPlaceReverse(firstReversed);
}

private String inPlaceReverse(String str) {
if (str == null || str.length() == 0) return str;
char[] chars = str.trim().toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left ++;
right --;
}
return String.valueOf(chars);
}
``````

Rotate String

Same strategy.

## Conclusion

1. If array is sorted, try binary search
2. If array is not sorted, try sort it first
3. When you see ‘rotated array’, think of ‘list reverse’.