陣列查找值使用索引邏輯面試問題

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。