文档章节

数组中找到和为给定值的两个数

B
 BlueWoods
发布于 2015/08/16 16:58
字数 809
阅读 116
收藏 4

problem 167 & 170 from leetcode;

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

https://leetcode.com/problems/two-sum-iii-data-structure-design/

先来看简单的167:给定一个排好序的数组,以及一个值,找出数组中相加等于该值的两个数,假设这样的值始终存在;

这个只要依次遍历该数组,假设当前值为x,那么只需要在数组中找到value - x;如果存在,直接返回,如果不存在,检查下一个值;因为数组是sorted,所以第二步查找只需要log N的时间;最坏情况是 n * log N;

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];

    for(int i = 1; i <= numbers.length; i++) {
        int x = numbers[i - 1];
        int y = target - x;
        int j = Arrays.binarySearch(numbers, i, numbers.length, y);
        if(j >= i) {
            result[0] = i;
            result[1] = j + 1;
            break;
        }
    }

    return result;
}

题目170要求设计一种数据结构,支持add和find操作,下面是一个例子:

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

一开始我得想法是使用167的解法,add的时候,把输入加入到一个数组中,并且排好序;那么就可以直接使用167的find;但在输入很长的时候,很多的add和find,会TLE;简单的分析一下这种方式,(我使用的是insertion sort), 每次add排序,要O(n), 那么总的时间就是O(n * n);

后来我用AVL树,因为AVL树支持logN的insert/find操作;正好适合这个问题;以下是最终AC的代码:

public class TwoSum {
    List<Integer> numbers = new ArrayList<>();
    AVL avl = new AVL();

    public void add(int number) {
        avl.add(number);
        numbers.add(number);
    }

    public boolean find(int value) {
        for (int x : numbers) {
            int y = value - x;
            Node node = avl.find(y);
            if (node == null) {
                continue;
            }

            //when these two numbers equal, need to make sure there at least two numbers added;
            if (x == y && node.count == 1) {
                continue;
            }

            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        TwoSum twoSum = new TwoSum();

        twoSum.add(1);
        twoSum.add(2);
        System.out.println(twoSum.find(1));
    }

    class AVL {
        Node root;

        private int height(Node root) {
            if (root == null) {
                return -1;
            } else {
                return root.height;
            }
        }

        private Node insert(Node root, int value) {
            if (root == null) {
                root = new Node(value);
            } else if (root.value == value) {
                root.count += 1;
            } else if (root.value < value) {
                //go right;
                root.right = insert(root.right, value);
                if (height(root.right) - height(root.left) == 2) {
                    if (value > root.right.value) {
                        root = singleRotateWithRight(root);
                    } else {
                        root = doubleRotateWithRight(root);
                    }
                }
            } else {
                //go left;
                root.left = insert(root.left, value);
                if (height(root.left) - height(root.right) == 2) {
                    if (value < root.left.value) {
                        root = singleRotateWithLeft(root);
                    } else {
                        root = doubleRotateWithLeft(root);
                    }
                }
            }

            root.height = Math.max(height(root.left), height(root.right)) + 1;
            return root;
        }

        private Node doubleRotateWithRight(Node k3) {
            k3.right = singleRotateWithLeft(k3.right);
            return singleRotateWithRight(k3);
        }

        private Node singleRotateWithRight(Node k2) {
            Node k1 = k2.right;
            k2.right = k1.left;
            k1.left = k2;

            k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
            k1.height = Math.max(height(k1.left), height(k1.right)) + 1;

            return k1;
        }

        private Node doubleRotateWithLeft(Node k3) {
            k3.left = singleRotateWithRight(k3.left);
            return singleRotateWithLeft(k3);
        }

        private Node singleRotateWithLeft(Node k2) {
            Node k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;

            k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
            k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
            return k1;
        }

        public void add(int value) {
            root = insert(root, value);
        }

        private Node find(Node root, int value) {
            if (root == null) {
                return null;
            }

            if (root.value == value && root.count == 0) {
                return null;
            }

            if (root.value == value) {
                return root;
            }

            if (value > root.value) {
                return find(root.right, value);
            } else {
                return find(root.left, value);
            }
        }

        public Node find(int value) {
            return find(root, value);
        }

        public Node getRoot() {
            return root;
        }
    }

    static class Node {
        final int value;
        int count, height;
        Node left, right;

        Node(int value) {
            this.value = value;
            count = 1;
            height = 0;
        }
    }

}

果然这种方法非常的有效,似乎是Java里面最快的实现了;

BTW, AVL的实现是从教科书里面找出来的,直接去写,真没有这样的本事;


© 著作权归作者所有

B
粉丝 4
博文 39
码字总数 21286
作品 0
杭州
私信 提问
找出数组中两数之和为指定值的所有整数对

一,问题描述 给定一个整型数组(数组中的元素可重复),以及一个指定的值。打印出数组中两数之和为指定值的 所有整数对 思路1:可以用hash表来存储数组中的元素,这样我们取得一个数后,去判...

一贱书生
2016/11/28
465
0
LeetCode算法题-Set Mismatch(Java实现)

这是悦乐书的第279次更新,第295篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第147题(顺位题号是645)。集合S最初包含从1到n的数字。 但不幸的是,由于数据错误,集合中的...

小川94
03/17
0
0
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0
LeetCode----Two Sum(两个数的和)

1、题目名称 Two Sum(两个数的和) 2、题目地址 https://leetcode.com/problems/two-sum/ 3、题目内容 Given an array of integers, return indices of the two numbers such that they add u......

笨拙的小Q
2016/03/10
276
0
Lintcode58 4Sum solution 题解

【题目描述】 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?Find all unique quadruplets in the array which gives the sum......

Winnielyn
2018/06/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

golang-字符串-地址分析

demo package mainimport "fmt"func main() {str := "map.baidu.com"fmt.Println(&str, str)str = str[0:5]fmt.Println(&str, str)str = "abc"fmt.Println(&s......

李琼涛
今天
4
0
Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
今天
6
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
今天
4
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
今天
5
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部