* Return the smallest character that is strictly larger than the search character,
* If no such character exists, return the smallest character in the array
* @param sortedStr : sorted list of letters, sorted in ascending order.
* @param c : character for which we are searching.
* Given the following inputs we expect the corresponding output:
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
* ['c', 'f', 'j', 'p', 'v'], 'c' => 'f'
* ['c', 'f', 'j', 'p', 'v'], 'k' => 'p'
* ['c', 'f', 'j', 'p', 'v'], 'z' => 'c' // The wrap around case
* ['c', 'f', 'k'], 'f' => 'k'
* ['c', 'f', 'k'], 'c' => 'f'
* ['c', 'f', 'k'], 'd' => 'f'
*/
Click here for the original problem.
The problem doesn't clarify if duplicates are allowed in the array. So I wrote two.
public class SmallestCharacter { public char nextChar(char[] list, char c) { if (list == null || list.length == 0) throw new IllegalArgumentException("Null or empty list!"); int start = 0; int end = list.length - 1; if (c < list[0] || c >= list[list.length - 1]) return list[0]; while (start < end) { int mid = (start + end) / 2; if (c == list[mid]) { //System.out.println(mid + ": " + list[mid]); return list[mid + 1]; } else if (c < list[mid]) { //System.out.println("smaller: " + mid); end = mid - 1; } else { //System.out.println("greater: " + mid); start = mid + 1; } } if (list[start] == c) return list[start + 1]; return list[start]; } }
Duplicates are allowed (not much difference though...)
public char nextChar2(char[] list, char c) { if (list == null || list.length == 0) throw new IllegalArgumentException("Null or empty list!"); int start = 0; int end = list.length - 1; if (c < list[0] || c >= list[list.length - 1]) return list[0]; while (start < end) { int mid = (start + end) / 2; if (c == list[mid]) { if (list[mid + 1] > c) return list[mid + 1]; else start = mid + 1; } else if (c < list[mid]) { end = mid - 1; } else start = mid + 1; } if (list[start] == c) return list[start + 1]; return list[start]; }
No comments:
Post a Comment