告诉了有序，还要求复杂度为logn，肯定二分了。
注意，每次下标可能为奇数、偶数，是奇数的话就要判断左边的数是否和它相同；是偶数的话就要判断右边的数是否和它相同。
class Solution { public int singleNonDuplicate(int[] nums) { int left = 0; int right = nums.length - 1; int mid; while (left < right) { mid = left + (right - left) / 2; if (mid % 2 == 0) { // 下标为偶数情况 if (nums[mid] == nums[mid + 1]) { left = mid + 2; } else { // 注意这里应该是mid，而不是mid+1 // 因为只有一个元素出现一次，那么这个元素出现的位置一定是偶数位置 right = mid; } } else { // 下标为奇数情况 if (nums[mid] == nums[mid - 1]) { left = mid + 1; } else { right = mid; } } } return nums[left]; }}
写二分一定要注意while判断符号，left、mid的加减一。
二、最长公共前缀（简单）
每次找两个字符串的公共前缀，记录下每次的结果，下一次用这次的结果与下一个字符串相比较。
class Solution { public String longestCommonPrefix(String[] strs) { String tmp = strs[0]; for (int i = 1; i < strs.length; i++) { tmp = common(tmp, strs[i]); } return tmp; } String common(String a, String b) { int i = 0; for (i = 0; i < a.length() && i < b.length(); i++) { if (a.charAt(i) != b.charAt(i)) { break; } } return a.substring(0, i); } }
发现nSum问题，也是有模板的，有空总结一下。