class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else return mid;
}
return -1;
}
}
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else return mid;
}
return -1;
}
}
class Solution {
private int searchRange(int[] nums, int target, boolean isLeft) {
int left = 0;
int right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
//相等
if (isLeft) {
if (mid == 0 || nums[mid - 1] != target) {
return mid;
} else {
right = mid - 1;
}
} else {
if (mid == nums.length - 1 || nums[mid + 1] != target) {
return mid;
} else {
left = mid + 1;
}
}
}
}
return result;
}
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[] {-1, -1};
int leftIndex = searchRange(nums, target, true);
if (leftIndex == -1) return new int[] {-1, -1};
int rightIndex = searchRange(nums, target, false);
return new int[] {leftIndex, rightIndex};
}
}
class Solution {
public int mySqrt(int x) {
if (x == 0) return 0;
if (x == 1) return 1;
int left = 1;
int right = x / 2;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = x / mid;
if (val > mid) {
left = mid + 1;
} else if (val < mid) {
right = mid - 1;
} else return mid;
}
return right;
}
}
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int result = 0;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
int target = nums[i] + nums[j];
int left = j + 1;
int right = n - 1;
int k = j;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
//符合条件的
left = mid + 1;
k = mid;
} else {
right = mid - 1;
}
}
result += (k - j);
}
}
return result;
}
}
class Solution {
private void rever(int[] nums, int left, int right) {
while (left < right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
rever(nums, 0, n - 1);
rever(nums, 0, k - 1);
rever(nums, k, nums.length - 1);
}
}
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int length = m + n;
int i = 0;
int j = 0;
int left = 0;
int rigth = 0;
for (int k = 0; k <= length / 2; k++){
left = rigth;
if (i < m && j < n) {
if (nums1[i] < nums2[j]) {
rigth = nums1[i++];
} else {
rigth = nums2[j++];
}
} else if (i >= m) {
rigth = nums2[j++];
} else {
rigth = nums1[i++];
}
}
if (length % 2 == 0) {
return (left + rigth) / 2.0;
} else {
return rigth;
}
}
}
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int length = m + n;
int left = 0;
int rigth = m;
int res1 = 0;
int res2 = 0;
while (left <= rigth){
int mid1 = left + (rigth - left) / 2;
int mid2 = (length + 1) / 2 - mid1;
int l1 = mid1 == 0 ? Integer.MIN_VALUE : nums1[mid1 - 1];
int l2 = mid2 == 0 ? Integer.MIN_VALUE : nums2[mid2 - 1];
int r1 = mid1 == m ? Integer.MAX_VALUE : nums1[mid1];
int r2 = mid2 == n ? Integer.MAX_VALUE : nums2[mid2];
if (l1 > r2) {
rigth = mid1 - 1;
} else if (l2 > r1) {
left = mid1 + 1;
} else {
res1 = Math.max(l1, l2);
res2 = Math.min(r1, r2);
break;
}
}
if (length % 2 == 0) return (res1 + res2) / 2.0;
else return res1;
}
}
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int rigth = nums.length - 1;
while (left <= rigth){
int mid = left + (rigth - left) / 2;
if (target == nums[mid]){
return mid;
} else if (nums[rigth] > nums[mid]) {
//右边有序
if (nums[mid] < target && target <= nums[rigth]) {
left = mid + 1;
} else {
rigth = mid - 1;
}
} else {
//左边有序
if (nums[left] <= target && target < nums[mid]) {
rigth = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
}
class Solution {
public boolean search(int[] nums, int target) {
int left = 0;
int rigth = nums.length - 1;
while (left <= rigth){
int mid = left + (rigth - left) / 2;
if (nums[mid] == target) return true;
else if (nums[mid] == nums[rigth]) {
rigth--;
} else if (nums[mid] == nums[left]) {
left++;
} else if (nums[mid] < nums[rigth]) {
if (nums[mid] < target && target <= nums[rigth]) {
left = mid + 1;
} else {
rigth = mid - 1;
}
} else {
if (nums[mid] > target && target >= nums[left]) {
rigth = mid - 1;
} else {
left = mid + 1;
}
}
}
return false;
}
}
class Solution {
public int search(int[] nums, int target) {
if (target == nums[0]) return 0;
int left = 0;
int rigth = nums.length - 1;
while (left <= rigth) {
int mid = left + (rigth - left) / 2;
if (nums[mid] == target) {
if (mid == 0 || target != nums[mid - 1]) return mid;
rigth = mid - 1;
} else if (nums[mid] == nums[left]) {
left++;
} else if (nums[mid] == nums[rigth]) {
rigth--;
} else if (nums[mid] < nums[rigth]) {
if (nums[mid] < target && target <= nums[rigth]) {
left = mid + 1;
} else {
rigth = mid - 1;
}
} else {
if (nums[mid] > target && target >= nums[left]) {
rigth = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
}
class Solution {
public int findMin(int[] nums) {
int low = 0;
int hight = nums.length - 1;
while (low < hight) {
int mid = low + (hight - low) / 2;
if (nums[mid] < nums[hight]) {
hight = mid;
} else {
low = mid + 1;
}
}
return nums[low];
}
}
class Solution {
public int findMin(int[] nums) {
int left = 0;
int rigth = nums.length - 1;
while (left < rigth) {
int mid = left + (rigth - left) / 2;
if (nums[mid] > nums[rigth]) {
left = mid + 1;
} else if (nums[mid] < nums[rigth]) {
rigth = mid;
} else if (nums[mid] == nums[rigth]) {
rigth--;
}
}
return nums[left];
}
}
网友评论