用指针实现逆序存放数组的值（二分思想的巧用）
用指针实现逆序存放数组的值（二分思想的巧用）所以. 我们可以看看下面这个图.比如[1 1 2]. 那么arr[1]!=arr[2] . 我们就记录下来.那么这要是能解决问题 就好了. O(n)其实很低了. 但是还能更低. 那就是 二分的作用.代码如下.public class Solution { // 返回 public Map<Integer Integer> findIndex(int[] arr) { Map<Integer Integer> map = new HashMap<>(); map.put(arr[0] 0); helper(arr 0 arr.length - 1 map); return map; } // 二分过程. public void hel
题目是 : 给定一个数组 已经排好序了. 此时要求返回 重复数组中 重复数组元素出现的第一个位置的索引
比如 [1 1 1 2 2 2 3 3 3] 输出 [0 3 6] 这里输出没有限制. 可以是k-v 其他 没说. 反正解决问题
有许多人 第一点 set么 看看有没有. 有加不添加. 最优是 O(n)
还有就是遍历一遍 保存状态量. 那么也是 O(n) 那么空间复杂度是 O(1)
那么这要是能解决问题 就好了. O(n)其实很低了. 但是还能更低. 那就是 二分的作用.
代码如下.
public class Solution {
// 返回
public Map<Integer Integer> findIndex(int[] arr) {
Map<Integer Integer> map = new HashMap<>();
map.put(arr[0] 0);
helper(arr 0 arr.length - 1 map);
return map;
}
// 二分过程.
public void helper(int[] arr int start int end Map<Integer Integer> map) {
if (start == end) return;
int mid = (start end) / 2;
if (arr[mid] != arr[mid 1]) {
map.put(arr[mid 1] mid 1);
}
helper(arr start mid map);
helper(arr mid 1 end map);
}
}
我们可以发现. 一个规律 其实节点. 如果这个节点与这个节点的后一个节点值不同时 他一定是第一次出现的. 因为是循序的么
比如[1 1 2]. 那么arr[1]!=arr[2] . 我们就记录下来.
所以. 我们可以看看下面这个图.
就是这个了. 你对于二分查找的理解是什么呢 ? . 这个就是最好的理解.
其实还有一种方法. 二分 归并. 其实我没有优化好 这种复杂度比传统的要高 . 是 nlog(n) .
