本文主要是介绍给定一个有序数组arr，代表坐落在X轴上的点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*** 题目：* 给定一个有序数组arr，代表坐落在X轴上的点* 给定一个正数K，代表绳子的长度* 返回绳子最多压中几个点？* 即使绳子边缘处盖住点也算盖住*/
public class Code01_CordCoverMaxPoint {//算法1 贪心+二分public static int maxPoint1(int[] arr, int L) {int res = 1;for (int i = 0; i < arr.length; i++) {//算出当前点像前最多能压几个点int nearest = nearestIndex(arr, i, arr[i] - L);res = Math.max(res, i - nearest + 1);}return res;}// R当前下标志 value 是要找的值public static int nearestIndex(int[] arr, int R, int value) {int L = 0;int index = R;while (L <= R) {//>>位移 右移int mid = L + ((R - L) >> 1);if (arr[mid] >= value) {index = mid;R = mid - 1;} else {L = mid + 1;}}return index;}//算法2 窗口法public static int maxPoint2(int[] arr, int L) {int left = 0;int right = 0;int N = arr.length;int max = 0;//假定窗口left 到right 判断每个点到后面最多能盖几个点，然后每个点都出个结果，比较最大的while (left < N) {//当前点根据绳子长度像后覆盖点，直到 没有数 可以延伸或者 大于绳子长度Lwhile (right < N && arr[right] - arr[left] <= L) {right++;}//比较旧覆盖点和新覆盖点哪个大就留哪个max = Math.max(max, right - (left++));}//关键是right不会向后退，就像个窗口一样，而算法一需要每次都二分去查找覆盖的点return max;}// for test 测试算法public static int test(int[] arr, int L) {int max = 0;for (int i = 0; i < arr.length; i++) {int pre = i - 1;while (pre >= 0 && arr[i] - arr[pre] <= L) {pre--;}max = Math.max(max, i - pre);}return max;}// for test 获取数组public static int[] generateArray(int len, int max) {int[] ans = new int[(int) (Math.random() * len) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = (int) (Math.random() * max);}Arrays.sort(ans);return ans;}public static void main(String[] args) {//数组长度100个int len = 100;//随机数大小1-到1000int max = 1000;//测试次数int testTime = 100000;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {//随机绳子长度int L = (int) (Math.random() * max);//生成数组int[] arr = generateArray(len, max);//测试算法1int ans1 = maxPoint1(arr, L);//测试算法2int ans2 = maxPoint2(arr, L);//暴力测试int ans3 = test(arr, L);if (ans1 != ans2 || ans2 != ans3) {System.out.println("oops!");break;}}}}
这篇关于给定一个有序数组arr，代表坐落在X轴上的点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
