文档章节

Java面试题(判断集合中是否有两个数的和等于某个给定整数)

lar555
 lar555
发布于 2016/06/07 15:53
字数 707
阅读 89
收藏 0

首先是参考思路:

解法1

解题步骤:

1.        对数组S进行归并排序。

2.        构造数组S’={z : z=x-y, y∈S},并排序。由于S已经有序,构造与排序可一并完成。

3.        删除S中重复的元素使仅保留一个,对S’进行同样的操作。

4.        合并S和S’,并保证合并后有序,这里可以使用归并排序的思想。

5.        如果在合并后的数组中存在连续两个相同的元素,并且这种元素的个数大于1,那么有解。

设想在合并后的数组中存在连续两个w,则w分别属于S和S’,那么S中存在y使得w=x-y,即x=y+w。因此,S中元素w和y的和为x。

步骤1的运行时间为Θ(n lg n),其余步骤运行时间为Θ(n),因此总的时间代价为Θ(n lg n)。

 

解法2:

对S排个序O(nlgn),然后用两个指针p1,p2分别指向头尾,

if(p1+p2 == x)
  return true;
else if(p1 + p2 > x)
  p2--;
else
  p1++;

直到2指针相遇,如果没有找到,返回false

 

解法3

如果x不大的话.

申请x大小的数组byte t[x],memset 0.

遍历下集合S,对于小于x的数i将t[i]=1; 这是0(N);

然后对数组t[x]遍历. 循环查找i对应的t[x-i]是否为1. 这是O(X)

 

相比较三种解题思路,首先第三种局限较大,没有前两种实现实用。第二种实现指针的方式一般适用于C/C++解题。第一种是一个很好的想法,所以我实现了第一种的java解法。下面是实现代码

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

public class TestSet {

    public static void main(String[] args) {
        int X = 30; //给定整数
        int[] S = {2,9,7,11,45,13,18,16,20,22,25,26,27,30};  // 原始集合
        Arrays.sort(S); //数组排序
        int length = S.length;
        int[] S1 = new int[length];     
        for (int i = 0 ; i < S.length; i++) {
                S1[i] = X - S[i];
        }
        System.out.println(Arrays.toString(S));
        Arrays.sort(S1);
        System.out.println(Arrays.toString(S1));

        int[] SS = delNum(S);   //数组去重
        int[] SS1 = delNum(S1);

        int[] Test = new int[SS.length + SS1.length];   //结果数组
        System.arraycopy(SS,0,Test,0,SS.length);
        System.arraycopy(SS1,0,Test,SS.length,SS1.length);
        Arrays.sort(Test);
        System.out.println(Arrays.toString(Test));

        int result = 0 ;
        for(int i = 0 ;i< Test.length-1; i++){  
            if(Test[i] == Test[i+1]){
                result ++;
            }
        }
        if(result == 0){
            System.out.println(" false" );
        }else{
            System.out.println(" ture " + result);
        }

    }

    private static int[] delNum(int[] s) {
        Set<Integer> set = new TreeSet<Integer>();  //Set 集合实现去重。
        for (int i : s) {   
            set.add(i);
        }
        int j = 0;
        int[] SS = new int[set.size()];
        for (Integer i : set) {
            SS[j++] = i;
        }
        System.out.println(Arrays.toString(SS));
        return SS;
    }

}

© 著作权归作者所有

共有 人打赏支持
lar555
粉丝 7
博文 64
码字总数 44559
作品 0
西安
程序员
私信 提问
【算法】LeetCode算法题-Two Sum

程序 = 数据结构 + 算法。 算法是每一位程序员学习成长之路上无法避开的重要一环,并且越早接触越好。今后会每天做些算法题,至少每天做一道题目,同时会记录自己的解题思路和代码,通过【算...

小川94
2018/10/15
0
0
LeetCode算法题-Power of Four(Java实现-六种解法)

这是悦乐书的第205次更新,第216篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第72题(顺位题号是342)。给定一个整数(带符号的32位),写一个函数来检查它是否为4的幂。例...

小川94
2018/12/18
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
2018/10/02
0
0
Java 面试题:百度前200页都在这里了

基本概念 操作系统中 heap 和 stack 的区别 什么是基于注解的切面实现 什么是 对象/关系 映射集成模块 什么是 Java 的反射机制 什么是 ACID BS与CS的联系与区别 Cookie 和 Session的区别 fa...

Java红茶
2017/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

组合问题(先提取数字+全组合)

今天在网上看到一个问题:想从A,B,C,D,E字母中选取3个A,B,C;并做出全组合ABC,ACB,BAC,BCA,CBA,CAB。这样的结果会有多少? 想法也是和问题一致: 1. 先从数列中选取所需要的值: A,B,C,D,E中选取...

tedzheng
16分钟前
0
0
vi常用命令

记录存档用,如下: 1、打开命令: vi+filename 2、退出命令: :q 退出而且不保存修改的内容 :q! 强制退出不保存修改的内容 :wq 退出并且保存修改的内容 :wq! 强制保存修改的内容然后退出...

ZICK_ZEON
17分钟前
1
0
查看Mysql正在执行的事务、锁、等待

一、关于锁的三张表(MEMORY引擎) ## 当前运行的所有事务mysql> select * from information_schema.innodb_trx\G;*************************** 1. row *************************** ......

吴伟祥
17分钟前
2
0
判断ifream 是否加载完成

$(function(){var iframe = document.getElementById("mainFrames"); if (iframe.attachEvent){ iframe.attachEvent("onload", function(){ //你要做的事}); }els......

卖星星的小矮人
20分钟前
1
0
11 Git —— 自定义Git

11 Git —— 自定义Git 忽略特殊文件 有些时候,你必须把某些文件放到Git工作目录中,但又不能提交它们,比如保存了数据库密码的配置文件啦,等等,每次git status都会显示Untracked files ....

lwenhao
27分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部