数字查找

[编程题]数字查找

热度指数：292 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为n的数组a[0],a[1]...a[n-1]和一个数字x，在数组中查找两个数a和b（可以是相同的值，但是不可以是相同位置的数字），使得它们的和与输入的数字差的绝对值最小。

比如：

a = [8,3,6,1] x=13

那么答案为：6和8

输入描述:

第一行两个数字 n，x（2<=n<=1000，1<=x<=10⁸）
第二行n个用空格隔开的数字a[0],a[1]...a[n-1]

输出描述:

两个数字a，b，用空格隔开。比较小的数字在左边，即输出要保证a<=b

示例1

输入

4 13
8 3 6 1

输出

6 8

算法知识视频讲解

进步不生锈

public static int[] Findmincha(int[] a ,int x) {
		int[] res = new int[2];
		Arrays.sort(a);
		//System.out.println("x:"+x);
//		for (int i = 0; i <a.length; i++) {
//			System.out.println("a["+i+"]:"+a[i]);
//		}		
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < a.length; i++) {
			for (int j = i+1; j < a.length; j++) {
				if (Math.abs(a[i]+a[j]-x)<min) {
					min = Math.abs(a[i]+a[j]-x);
					res[0]=a[i];
					res[1]=a[j];
				}
			}
		}
		//System.out.print(res[0]+" "+res[1]);
		return res;
		
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();		
		int[] a =new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i]=sc.nextInt();
		}
		int[] res = Findmincha(a,x);
		System.out.print(res[0]+" "+res[1]);

	}

这题只能一种答案，如果有两种答案的话，还不能选另一种？比如 3+4=7，2+5=7，但是选了另一种会报错，所以我的代码没有通过

发表于 2020-02-11 20:42:46 回复(0)

顶呱呱的奶糖很爱吃鸡腿

双指针对有序数组查找指定值，小改即可（但是测试用例有问题答案不唯一，不能通过）

n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
st, ed = 0, n-1
a.sort()
temp = float('inf')
ans = []
while st<ed:
    now = a[st]+a[ed]
    if now>x:
        if now-x<temp:
            temp=now-x
            ans = [a[st],a[ed]]
        ed-=1
    elif now<x:
        if x-now<temp:
            temp=x-now
            ans = [a[st],a[ed]]
        st+=1
    else:
        ans = [a[st],a[ed]]
        break
print(*ans)

发表于 2023-08-08 00:31:55 回复(0)

牛客703413254号

import sys

a = [[0],[0]]
i = 0
for line in sys.stdin:
    # print(line)
    # a = line.strip('\n')
    b = line.split('\n')[0]
    b = b.split(' ')
    a[i] = b
    i += 1

tmp = {}
for i in range(int(a[0][0])):
    for j in range(i+1, int(a[0][0])):
        tmp[int(a[1][i])+int(a[1][j])] = (a[1][i], a[1][j])
tar1 = int(a[0][1])
tar2 = tar1
x = '0'
y = '0'
while 1:
    if tar1 in tmp:
        x, y = tmp[tar1]
        break
    if tar2 in tmp:
        x, y = tmp[tar2]
        break
    else:
        tar1 = tar1+1
        tar2 = tar2-1 
l = []
l.append(int(x))
l.append(int(y))
l.sort()
# print(l)
print(l[0],l[1])

坑p问题，明明没说有多种情况怎么办，还答案只有一种情况，有多种情况时输出其他情况就算错，又不说清楚选择的标准是啥，我怎么知道什么算对什么算错

发表于 2023-03-27 22:37:15 回复(1)

myshrry

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    sort(nums.begin(), nums.end());
    int greater = INT_MAX, smaller = INT_MIN;
    int gArr[2], sArr[2];
    // 双指针
    int left = 0, right = n - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum > target) {
            if (sum < greater) {
                greater = sum;
                gArr[0] = nums[left];
                gArr[1] = nums[right];
            }
            right--;
        }
        else if (sum < target) {
            if (sum > smaller) {
                smaller = sum;
                sArr[0] = nums[left];
                sArr[1] = nums[right];
            }
            left++;
        }
        else {
            printf("%d %d", nums[left], nums[right]);
            return 0;
        }
    }
    if (abs(smaller - target) < abs(greater - target)) printf("%d %d", sArr[0], sArr[1]);
    else printf("%d %d", gArr[0], gArr[1]);

    return 0;
}
// 64 位输出请用 printf("%lld")

// 答案不止一组，输出另一组还报错，就离谱

编辑于 2023-01-25 01:44:24 回复(0)

你永远得不到的祖奶奶

# str1=input()
# str2=input()

input1=str(input()).split(' ')
n,x=int(input1[0]),int(input1[1])
number1 = str(input()).split(' ')
number=[int(item) for item in number1]
num_abs = {}
for i in range(n-1):
    for j in range(i+1, n):
        list1=[]
        append_num = abs(number[i]+number[j]-x)
        if number[i]>number[j]:
            list1.append(number[j])
            list1.append(number[i])
        else:
            list1.append(number[i])
            list1.append(number[j])
        num_abs[append_num]=list1
# print(num_abs)
min_num=min(num_abs.keys())
# print(min_num)
# print(type(num_abs[min_num]))
min_value1=num_abs[min_num]
min_value=[str(item) for item in min_value1]
#print(min_value=num_abs[min_num])
print(' '.join(min_value))

编辑于 2022-06-21 16:30:42 回复(0)

Buendia94

n,x = list(map(int, input().split(' ')))
A = [int(x) for x in input().split(' ')]
num = len(A)
a = 0
b = 1
for i in range(num - 1):
for j in range(i+1, num):
if abs(A[i] + A[j] - x) < abs(A[a] + A[b] - x):
a = i
b = j
if A[a] < A[b]:
print(A[a], A[b])
else:
print(A[b], A[a])

发表于 2020-06-10 22:54:15 回复(0)

Java

覔亖甴愢丢

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main {
    static int[] array1;
    public static void main(String[] args) {
        //输入两个数  数组大小n  要比较的数x
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
 
        //数组array1
        if (2 <= n && n <= 1000 && 1 <= x && x <= 10E8) {
            array1 = new int[n];
            for (int i = 0; i < n; i++) {
                int b = sc.nextInt();
                array1[i] = b;
            }
 
            //结果放进map
            Map map = new HashMap();
            int c;
            int e=1000000;
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    //去重
                    if (i == j || i > j) {
                        continue;
                    }
                    c = Math.abs(array1[i] + array1[j]- x);
 
                    map.put(c, Math.min(array1[i],array1[j]) + "," +Math.max(array1[i],array1[j]) );
                    e = Math.min(e, c);
                }
            }
 
//            System.err.println("最小绝对值"+e);
            StringTokenizer splitor = new StringTokenizer((String) map.get(e),",");
            while(splitor.hasMoreTokens()){
                System.out.print(splitor.nextElement()+" ");
            }
        }
    }
}

发表于 2020-02-19 19:40:38 回复(0)