有這樣一個(gè)數(shù)組A，大小為n，相鄰元素差的絕對(duì)值都是1。

發(fā)布時(shí)間：2020-07-21 20:35:23 來源：網(wǎng)絡(luò) 閱讀：1685 作者：小止1995 欄目：編程語言

有這樣一個(gè)數(shù)組A，大小為n，相鄰元素差的絕對(duì)值都是1。如：A={4,5,6,5,6,7,8,9,10,9}。現(xiàn)在，給定A和目標(biāo)整數(shù)t，請(qǐng)找到t在A中的位置。除了依次遍歷，還有更好的方法么？

思路：數(shù)組第一個(gè)數(shù)為array[0], 要找的數(shù)為y，設(shè)t = abs(y - array[0])。由于每個(gè)相鄰的數(shù)字之差的絕對(duì)值為1。故第t個(gè)位置之前的數(shù)肯定都比y小。因此直接定位到array[t]，重新計(jì)算t，t = abs(y – array[t])，再重復(fù)上述步驟即可。這種算法主要利用了當(dāng)前位置的數(shù)與查找數(shù)的差來實(shí)現(xiàn)跨越式搜索。算法效率要比遍歷數(shù)組的算法要高一些，并且易于實(shí)現(xiàn)。

int FindNumberInArray(int arr[], int n , int find_number)  
{  
  int next_arrive_index = abs(find_number - arr[0]);  
  while (next_arrive_index < n)  
  {  
    if (arr[next_arrive_index] == find_number)  
      return next_arrive_index;  
    next_arrive_index += abs(find_number - arr[next_arrive_index]);  
  }  
  return -1;  
}

拓展：有一個(gè)int型數(shù)組，每兩個(gè)相鄰的數(shù)之間的差值不是1就是-1.現(xiàn)在給定一個(gè)數(shù)，要求查找這個(gè)數(shù)在數(shù)組中的位置。

向AI問一下細(xì)節(jié)

有這樣一個(gè)數(shù)組A，大小為n，相鄰元素差的絕對(duì)值都是1。

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽

有這樣一個(gè)數(shù)組A，大小為n，相鄰元素差的絕對(duì)值都是1。