一道算法编程题

public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
for(int i=200;i<1000;i++){
list.add(i+1);
}
for(int i=0;i<200;i++){
list.add(i+1);
}
int temp = new Random().nextInt(1000);
int i=0;
int j=list.size()-1;
System.out.println(temp);
while((j-i)>2){
int k = (j+i)/2;
if(temp==list.get(i)){
break;
}
if(temp > list.get(i)){
if(temp>list.get(k)){
if(list.get(k)>list.get(i)){
i=k;
}else{
j=k;
}
}else{
j=k;
}
}else{
if(temp < list.get(k)){
if(list.get(k)>list.get(i)){
i=k;
}else{
j=k;
}
}else{
i=k;
}
}
}
while(i<=j){
if(list.get(i)==temp){
break;
}
i++;
}
System.out.println(i);

}

public class c extends f{

    public static void main(String[] args) {
int[] source = {1,2,3,4,5,6,7,8,9,10};
int size = source.length;
int tmp = new Random().nextInt(10);
if(tmp > size)
{
    System.out.println("truncate number is out size of length of array");
    return;
}
else
{
    int[] tmparr = new int[size];
    int k = 0;
    for(int i = tmp; i < size; i ++)
    {
tmparr[k++] = source[i];
    }
    for(int j = 0; j < tmp; j++)
    {
tmparr[k++] = source[j];
    }
    source = tmparr;
}
for(int i = 0;i < size; i++)
{
    System.out.print(source[i]);
}
    }
}

O(N)以下O(1),不太可能吧，怎么也得河长度有关。
先把前N个翻转，然后后面那些翻转，最后全部翻转一下这个算法是O(n)。
系数也不算大，代码如下。package lesson11_1_1;public class Wan {
    int numbers[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

    void Cut(int position)
    {
     Reverse(0,position - 1);
     Reverse(position, numbers.length - 1);
     Reverse(0, numbers.length - 1);
    }


    void Reverse(int start, int end)
    {
     int i = start, j = end;
     while(i < j)
     {
     int temp = numbers[i];
     numbers[i] = numbers[j];
     numbers[j] = temp;

     ++ i;
     -- j;
     }
    }
public static void main(String[] args)
{
// TODO Auto-generated method stub
Wan w = new Wan();
w.Cut(7);
for(int i = 0; i < w.numbers.length; ++i)
System.out.println(w.numbers[i] + " "); }}

不好意思啊。题意理解错了。。
这不是更简单直接上二分查找不就OK了。
先找到二分找到两段分界点，之后进行比较大的话在前面找，小的话在后面找复杂度是O(log n)
package lesson11_1_1;public class Wan {
    static int numbers[] = {19, 23, 29, 31, 37, 2, 3, 5, 7, 11, 13, 17};



    static int BinSearch1()
    {//找分界点
     int start = 0;
     int end = numbers.length - 1;
     int middle =  0;

     while(numbers[start] > numbers[end])
     {
     if(end - start == 1)
     break;

     middle = (start + end) / 2;

     if(numbers[middle] > numbers[start])
     start = middle;
     else
     end = middle;
     }

     return start;
    }

    static int BinSearch2(int start, int end, int value)
    {
     if(value == numbers[start])
     return start;
     if(value == numbers[end])
     return end;

     int middle = (start + end) / 2;
     while(start < end)
     {
     if(numbers[middle] == value)
         break;

     else if(numbers[middle] > value)
     end = middle - 1;
     else
     start = middle + 1;

     middle = (start + end) / 2;
     }
     return middle;
    }

    static int Search(int value)
    {
     int cut = BinSearch1();


     if(value >= numbers[0])
     return BinSearch2(0,cut, value);
     else
     return BinSearch2(cut + 1, numbers.length - 1, value);

    }
public static void main(String[] args)
{
// TODO Auto-generated method stub

System.out.println(Search(23)); }}

知道关键字在原数组的位置就好办了啊，比如是7
二分查找就行了。
先和数组的第一个数比较，大于这个数就在0,7之间二分查找
否则就在8，end之间二分查找

取数组第一个元素，比较，
如果待查元素比第一个元素大、则向后比较查找，直到数组后续元素比前一个元素小；
如果待查元素比第一个元素小、则从数组末尾向前开始查找，直到数组前序元素比当前大。算法时间复杂度应该近似O(n)而不等O(n)吧？

调试易

一道算法编程题

解决方案 »