数据结构存储整数范围，查询范围并修改范围 [英] Data Structure to store Integer Range , Query the ranges and modify the ranges

问题描述

我们需要保持mobileNumber及其在内存中的位置。
挑战是我们有超过500万的用户
，并且存储每个用户的位置将如同500万条记录的哈希映射。
要解决这个问题，我们必须在范围工作

我们给出了一些电话号码范围，如

• range1 start =9899123446end =9912345678location =a




• range2 start = 9912345679end =9999999999location =b

一个数字只能属于单个位置。 / p>

我们需要一个数据结构将这些范围存储在内存中。

它必须支持两个函数p>

1. findLocation（整数）它应该将位置名称返回到
   ，该数字属于


2. changeLocation（整数，字符串范围）。它将数字的位置从旧位置更改为新位置

这是完全在内存设计中。

我正在计划使用树结构，每个节点包含（startofrange，endofrange，location）。
我将按排序顺序保存节点。我还没有完成任务。
主要问题是 - 当第二个功能更改位置被称为9899123448位置到b

range1节点应该分为3个节点第一个节点（9899123446,9899123447，a）
第二个节点（9899123448,9899123448，b）第三个节点（9899123449,9912345678，a）。

请建议适当的方法
提前感谢

解决方案

通常，您可以使用专门的数据结构来存储范围并实现查询，例如间隔树。

但是，由于电话号码范围不重叠，您可以将范围存储在基于标准树的数据结构中（二进制搜索树， AVL树，红黑树 ， B树将全部工作）仅按[开始] 。

对于findLocation（number），使用相应的树搜索算法来找到[begin]值小于该数的第一个元素，检查其[end]值并验证数字是否在该范围内。如果找到匹配项，返回位置，否则数字不在任何范围内。

对于changeLocation（）操作：

1. 查找包含数字


2. 的旧节点如果在步骤1中找到现有节点，请删除它并插入新节点


3. 如果没有找到现有的节点，请插入一个新节点并尝试将其与相邻节点合并。

我假设您正在使用相同的操作来简单地添加新节点。

更实际地，您可以将所有条目存储在数据库中，在[begin]上构建索引。

We need to maintain mobileNumber and its location in memory. The challenge is that we have more than 5 million of users and storing the location for each user will be like hash map of 5 million records. To resolve this problem, we have to work on ranges

We are given ranges of phone numbers like

• range1 start="9899123446" end="9912345678" location="a"

• range2 start="9912345679" end="9999999999" location="b"

A number can belong to single location only.

We need a data structure to store these ranges in the memory.

It has to support two functions

1. findLocation(Integer number) it should return the location name to which number belongs
2. changeLocation( Integer Number , String range). It changes location of Number from old location to new location

This is completely in memory design.

I am planning to use tree structure with each node contains ( startofrange , endofrange ,location). I will keep the nodes in sorted order. I have not finalized anything yet. The main problem is-- when 2nd function to change location is called say 9899123448 location to b

The range1 node should split to 3 nodes 1st node (9899123446,9899123447,a) 2nd node (9899123448,9899123448,b) 3rd node (9899123449,9912345678,a).

Please suggest the suitable approach Thanks in advance

解决方案

Normally you can use specialized data structures to store ranges and implement the queries, e.g. Interval Tree.

However, since phone number ranges do not overlap, you can just store the ranges in a standard tree based data structure (Binary Search Tree, AVL Tree, Red-Black Tree, B Tree, would all work) sorted only by [begin].

For findLocation(number), use corresponding tree search algorithm to find the first element that has [begin] value smaller than the number, check its [end] value and verify if the number is in that range. If a match if found, return the location, otherwise the number is not in any range.

For changeLocation() operation:

1. Find the old node containing the number
2. If an existing node is found in step 1, delete it and insert new nodes
3. If no existing node is found, insert a new node and try to merge it with adjacent nodes.

I am assuming you are using the same operation for simply adding new nodes.

More practically, you can store all the entries in a database, build an index on [begin].

这篇关于数据结构存储整数范围，查询范围并修改范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！