Leetcode: Search Insert Position
LeetCode search INSERT position
2023-09-11 14:14:08 时间
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0
很简单的题目,一次过,注意为数组空的时候,应返回0而非null
1 public class Solution { 2 public int searchInsert(int[] A, int target) { 3 int i; 4 if (A.length == 0) return 0; 5 for (i=0; i<A.length; i++){ 6 if (target <= A[i]){ 7 return i; 8 } 9 } 10 return A.length; 11 } 12 }
binary search: 就是当循环结束时,如果没有找到目标元素,那么l一定停在恰好比目标大的index上,r一定停在恰好比目标小的index上
1 public int searchInsert(int[] A, int target) { 2 if(A == null || A.length == 0) 3 { 4 return 0; 5 } 6 int l = 0; 7 int r = A.length-1; 8 while(l<=r) 9 { 10 int mid = (l+r)/2; 11 if(A[mid]==target) 12 return mid; 13 if(A[mid]<target) 14 l = mid+1; 15 else 16 r = mid-1; 17 } 18 return l; 19 }
相关文章
- Leetcode 之Convert Sorted List to Binary Search Tree(55)
- Java实现 LeetCode 778 水位上升的泳池中游泳(二分+DFS)
- Java实现 LeetCode 687 最长同值路径(递归)
- Java实现 LeetCode 653 两数之和 IV - 输入 BST(递归,找差值)
- Java实现 LeetCode 648 单词替换(字典树)
- Java实现 LeetCode 459 重复的子字符串
- Java实现 LeetCode 450 删除二叉搜索树中的节点
- Java实现 LeetCode 405 数字转换为十六进制数
- Java实现 LeetCode 151 翻转字符串里的单词
- Java实现 LeetCode 87 扰乱字符串
- Java实现 LeetCode 4 寻找两个有序数组的中位数
- LeetCode(3):无重复字符的最长子串
- LeetCode-226. 翻转二叉树【递归】
- 91. 解码方法 ——【Leetcode每日刷题】
- Search a 2D Matrix -- LeetCode
- [LeetCode]235.Lowest Common Ancestor of a Binary Search Tree
- leetcode第一刷_Word Search
- LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)
- [LeetCode]Wildcard Matching 通配符匹配(贪心)
- Leetcode 733. 图像渲染(牛,做出来了)
- [LeetCode] 784. 字母大小写全排列 ☆☆☆(回溯、深度优先遍历)
- [LeetCode] 99. Recover Binary Search Tree(复原BST) ☆☆☆☆☆
- [LeetCode] 35. Search Insert Position ☆(丢失的数字)
- leetcode——Search a 2D Matrix 二维有序数组查找(AC)
- leetcode第一刷_Search in Rotated Sorted Array
- leetcode 501. Find Mode in Binary Search Tree
- leetcode 108. Convert Sorted Array to Binary Search Tree
- leetcode 669. Trim a Binary Search Tree
- 【LeetCode】221.最大正方形