阵列查找值使用索引逻辑面试问题

Question

以下给出阵列无限长度具有自然数，因为它可以是无限的长度：

int[] myArray = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3 ......}; 

//在地方的10它会采取1,0，在地方的11它会采取1，1，在位置12的它会采取1,2的等等.....

index 0 = > value 0 = > number 0 
index 1 = > value 1 = > number 1 
index 2 = > value 2 = > number 2 
index 3 = > value 3 = > number 3 
index 4 = > value 4 = > number 4 
index 5 = > value 5 = > number 5 
index 6 = > value 6 = > number 6 
index 7 = > value 7 = > number 7 
index 8 = > value 8 = > number 8 
index 9 = > value 9 = > number 9 
index 10 = > value 1 = > number 10 
index 11 = > value 0 = > number 10 
index 12 = > value 1 = > number 11 
index 13 = > value 1 = > number 11 
index 14 = > value 1 = > number 12 
index 15 = > value 2 = > number 12 

.... 
.... 
.... 

索引9值应为9，但在索引10而不是数值为10它应该是1 &再次在索引11值应该是0，然后在索引12值应该是1等等......

假设为索引值10，我们得到的结果为1，对于值11，我们得到的结果值0

我们必须写我们的逻辑得到通过传递索引值的值，指数可以从0〜10000000

我们不能直接使用数组在特定指数来获得价值，我们必须编写逻辑如下图所示：

public int getValue(int index){ 

    int value = 0; 

    // logic to find the the value 

    return value; 
} 

我曾尝试下面的方法来得到的结果为通过指数，但它工作到两位数字，即99（直到索引189）。但是对于三位数字&我们还需要更改逻辑。

public static int myMethod(int index){ 
    System.out.println("index : " + index); 

    if(index <= 9){ 
     return index; 
    } 

    boolean even = (index % 2) == 0; 

    int num = 0 ; 
    char res = 0; 
    if(even){ 
     num = index - ((index - 10)/2); 
     System.out.println("num " + num); 

     res = new Integer(num).toString().charAt(0);    
    }else{ 

     index = index -1; 
     num = index - ((index - 10)/2); 
     System.out.println("num 22 : " + num); 
     res = new Integer(num).toString().charAt(1);    
    } 

    int result = new Integer(res+""); 

    System.out.println(result); 
    return result ; 
} 

Answer 1

此功能（在JavaScript转换自己的Java），给出了一个索引x数量的length这个指数下位的position。

例如，对于索引15，它将返回{length: 2, pos: 1}，因为在索引15下存在12的2，所以相对于12的索引2是1，并且12的长度是2数字。

index: 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|.. 
value: 0|1|2|3|4|5|6|7|8|9|1 |0 |1 |1 |1 |2 |.. 

我想你可以编写代码来自己从数组中获取正确的值。

function find(x){ 
 
    var length = 0; 
 
    while(x > 0){ 
 
    length++; 
 
    x = x - (10**(length-1)) * length * 9; 
 
    } 
 
    return {length: length, pos: (x % length) + length -1}; 
 
} 
 

 
console.log(find(15));

Answer 2

该序列被称为Champernowne constant。

基本的方法是计算出所有1位数，2位数，3位数等等的总长度。一旦你知道哪个数字范围是合适的，就可以确定范围内的确切数字，那么数字中的确切数字。

有效算法的全部细节可以在this pdf中找到。

Answer 3

我想说我们从1开始而不是从0开始，使以下更简单（你可以从索引中减去1来包含它）。

让我们先从一些分析：

• 有9消耗的前9 * 1 = 9×10 * 1 = 9位1位数字（1-9）。
• 有90个2位数字（10-99）消耗接下来的90 * 2 = 9 * 10 * 2 = 180个位置。
• 有900个3位数字（100-999）消耗接下来的900 * 3 = 9 * 10 * 3 = 2700个位置。
• 等等

正如从上面可以看出，在n位数字占用9 * 10 ^n-1个 * n个位置。

从这里，它不是太难的一个指标转换成相应的数字：

• 循环在每个以上的情况下（用一个简单的for循环），减去位置相应数量的我们索引，直到这样做会给我们一个负数。
• 将我们的索引除以我们当前获得偏移量的位数，然后使用该位数（10的倍数）添加第一个值以找到我们要查找的数字。
• 要确定我们正在寻找的数字（如果不是查找整个数字），我们可以将我们上述的其余部分给我们我们的答案。

例如：

• 比方说，我们需要得到指数200的值（或201，如果从0开始）。
• 剔除1位数号码给我们200-9 = 191
• 剔除2位数字为我们提供了191-180 = 11
• 试图排除3位数号码将导致负号码，所以我们知道这是一个3位数字。
• 除以11的位数（3）给我们3（舍入）。
• 第3位（从0开始）3位数为100 + 3 = 103.
• 由于11％3 = 2，我们正在寻找第2位数（从0开始），所以3是我们的答案。

代码：

final int[] POWERS_OF_10 = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000}; 
int getValue(int index){ 
    if (index-- == 0) // remove this if-statement to start from 1 
     return 0; 
    int digits = 0; 
    int positions = 0; 
    while (positions <= index) 
    { 
     index -= positions; 
     digits++; 
     positions = 9 * digits * POWERS_OF_10[digits-1]; 
    } 
    int number = index/digits + POWERS_OF_10[digits-1]; 
    int digit = index % digits; 
    int value = Integer.toString(number).charAt(digit) - '0'; // lazy approach 
    // int value = number/POWERS_OF_10[digits-digit-1] % 10; // non-lazy approach 
    return value; 
} 

此：

for (int i = 0; i < 20; i++) 
    System.out.print(getValue(i) + ", "); 

会打印出：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 

Live demo。