狸猫的笔试——查找

短命女 2022-07-26 09:03 133阅读 0赞

输入：

一个递增排序的数组

一个数字S

要求：

在数组中查找两个数，使他们的和正好是S，如果有多对数字的和是S，则输出两个数乘积最小的

输出：

两个数

javaCode

最好情况下，时间复杂度为O(n/2)

public static void sum(int[] arr, int s) {
    		// 数组长度不够
    		if (arr.length <= 1) {
    			System.out.println("error");
    			return;
    		}
    		boolean mark = false;
    		// 让i、j指向数组的中间的两位
    		int i = arr.length / 2 - 1;
    		int j = i + 1;
    		// 将两个数初始化为arr的最大值
    		int num1 = arr[arr.length - 1] + 1;
    		int num2 = arr[arr.length - 1] + 1;
    		// 如果越界，或者i，j重合则结束
    		while (i >= 0 && j < arr.length && (i != j)) {
    			if (i == 0 && j == arr.length - 1)
    				mark = true;
    			// ==s时，i，j都往边缘走
    			if (arr[i] + arr[j] == s) {
    				if (arr[i] * arr[j] < num1 * num2) {
    					num1 = arr[i];
    					num2 = arr[j];
    				}
    				if (j == arr.length - 1 && i == j - 1)
    					break;
    				if (mark)
    					++i;
    				else
    					--i;
    			} else if (arr[i] + arr[j] > s) {
    				// 如果大于s，则i应减小
    				// 如果i移到边缘，则j应减小
    				if (i == 0)
    					--j;
    				else if (mark)
    					--j;
    				else
    					--i;
    			} else {
    				// 如果小于s 则j应增大
    				// 如果j移动到边缘，则i应增大
    				if (j >= arr.length - 1)
    					++i;
    				else if (mark)
    					++i;
    				else
    					++j;
    			}
    		}
    		// 如果num1 和 num
    		if (num1 + num2 == s) {
    			System.out.println(num1 + " " + num2);
    		} else {
    			System.out.println("Error" + num1 + " " + num2);
    		}
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关狸猫的面试——JVM内存回收

写在前面：详述JVM中内存管理机制以及GC机制内存组成： 1）堆所有通过new创建的对象的内存都在堆中分配，其大小可以通过-Xmx和-Xms来控制。堆被划分为新生代和

迷南。/ 2022年08月21日 14:54/ 0 赞/ 97 阅读

相关狸猫的面试——项目描述——视频通信

软件需求： 1.最大支持4人 2.能进行文本通信，视频通信。 3.用户上下线的通知软件设计： 2015/09/14 关于服务器与客户端线程处理的设想：

梦里梦外;/ 2022年08月21日 12:50/ 0 赞/ 112 阅读

相关狸猫的面试——链表

1.找出链表的中间元素解法：链表的特点是容易增删，难于随机访问。如果按照常规的想法：（1）遍历链表，获取长度（2）从头走1/2步。但是这种方式会需要O(1.

秒速五厘米/ 2022年07月30日 13:56/ 0 赞/ 99 阅读

相关狸猫的笔试——字符转int

public static int getInt(String s,int radix) throws Exception { if(s == n

约定不等于承诺〃/ 2022年07月28日 09:44/ 0 赞/ 125 阅读

相关狸猫的笔试——查找

输入：一个递增排序的数组一个数字S 要求：在数组中查找两个数，使他们的和正好是S，如果有多对数字的和是S，则输出两个数乘积最小的输出：两个数

短命女/ 2022年07月26日 09:03/ 0 赞/ 134 阅读

相关狸猫的笔试——镜像字符串（二叉树法）

输入一串字符串，获取其中最长的镜像字符串例如 cabecbad 对与子串:abecba 除去c 剩下 abeba即为最长的镜像字符串长度为5 算法思想：

喜欢ヅ旅行/ 2022年07月26日 06:18/ 0 赞/ 96 阅读

相关狸猫的笔试——格雷码判断

输入两个数，判断是否符合格雷码例如： 10 和11 为true 11 和 11 为false 11 和 00 为false public sta

ゝ一纸荒年。/ 2022年07月26日 06:17/ 0 赞/ 128 阅读

相关狸猫的笔试——蛇形矩阵

蛇形矩阵：一个n\n的矩阵，矩阵的内容成蛇形。例如 n=3; 矩阵内容： 1 2 3 8 9 4 7 6 5 按行输出为： 1 2 3 8 9 4 7 6 5

电玩女神/ 2022年07月26日 06:16/ 0 赞/ 137 阅读

相关狸猫的笔试——集合

1.计算1+2+3+……+n。不使用乘法。分析：这道题有三种思路。 1.用for循环从一加到n。虽然简单，但是时间最长。 2.根据等差数列公式有（1+n）\n/2

旧城等待，/ 2022年07月17日 02:12/ 0 赞/ 132 阅读

相关笔试记录--二分查找（Python）

宣讲后笔试题目：实现一个简单的二分查找，给出的数列是从小到大的。 '''二分查找''' def binary_search(num_list,x

﹏ヽ暗。殇╰゛Y/ 2022年05月09日 01:03/ 0 赞/ 158 阅读