网站建设的公司哪家强_运营方案包括哪些内容_谷歌关键词_当下最流行的营销方式

704. 二分查找

leetcode题目地址

经典二分查找思路，有序列表左右边界向中间夹逼。

时间复杂度： $O(logn)$
空间复杂度： $O(1)$

// java
class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length-1, mid;while(left<=right){mid = left + ((right - left) >> 1);if(nums[mid] == target) return mid;if(nums[mid] > target) right = mid - 1;else left = mid + 1;}return -1;/*// 暴力法for(int i=0; i<nums.length; i++){if(nums[i] == target) return i;}return -1;*/}
}

27. 移除元素

leetcode题目地址

双指针法。右指针负责遍历数组，左指针负责标记不等于val元素的列表末尾。
当右指针遇到非val元素时，将该元素赋值到左指针为止，两个指针同时后移。
当右指针遇到val元素时，左指针不动，右指针后移。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// java
class Solution {public int removeElement(int[] nums, int val) {int left = 0, right = 0;while(right<nums.length){if(nums[right] == val){right++;}else{nums[left] = nums[right];left++;right++;}}return left;}
}

977. 有序数组的平方

leetcode题目地址

思路1

这种写法比较繁琐。题目给定序列为非递减顺序，分三种情况：

• 全为正数
  直接正序平方存入结果数组。
• 全为负数
  逆序平方存入结果数组。
• 有正有负数
  找到正负数分界点，从中间向两边找较小值正序存入结果数组。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {public int[] sortedSquares(int[] nums) {int right = 0, left = 0;int[] res = new int[nums.length];int cnt = 0;if(nums[0]>0 && nums[0] * nums[nums.length-1]>0){// 正数单调递增序列for(int i=0; i<=nums.length-1; i++) res[cnt++] = nums[i] * nums[i]; }else if(nums[0]<0 && nums[0] * nums[nums.length-1]>0){// 正数单调递增序列for(int i=nums.length-1; i>=0; i--) res[cnt++] = nums[i] *nums[i]; }else{// 寻找分界点for(; right<nums.length && nums[right]<0; right++){}left = right-1;while(left>=0 && right <= nums.length-1){if(-nums[left] > nums[right]) {res[cnt++] = nums[right] * nums[right];right++;}else{res[cnt++] = nums[left] * nums[left];left--;}}while(left>=0){res[cnt++] = nums[left] * nums[left];left--;}while(right <= nums.length-1){res[cnt++] = nums[right] * nums[right];right++;}}return res;}
}

思路二

对思路一的反向思维。最复杂的情况就是数组中有正有负，这种情况下，平方后的最小值出现在正负分界点，最大值出现在列表的两端。因此之间从列表两端找平方后的最大值逆序存入结果列表。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {public int[] sortedSquares(int[] nums) {int left = 0, right = nums.length-1;int[] res = new int[nums.length];int idx = right;while(left<=right){if(Math.abs(nums[left]) > Math.abs(nums[right])){res[idx--] = nums[left] * nums[left];left++;}else{res[idx--] = nums[right] * nums[right];right--;}}return res;}
}