首页 > 试题广场 >

旋转排序数组搜索 ii

[编程题]旋转排序数组搜索 ii

热度指数：9046 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个非降序的数组 $a\$ ，对第 $i\$ 位之后的部分进行旋转（将 $a_{i+1}$ 及以后的部分按原数组顺序移到前面），即 $a\$ 中的元素满足 $a_0 \leq a _1 \leq a_i , a_{i+1} \leq a _{i+1} \leq a_n$ 。

例如，对于数组 $a=[1,3,4,4,5]\$ ，取 $i=2\$ 进行旋转，那么得到的数组是 $a=[4,4,5,1,2]\$

特殊的，若 $i=n\$ ，则原数组不发生任何改变。

现在给定一个数 $x\$ ，请你在数组 $a\$ 中搜索 $x\$ 是否存在。若存在则返回 true ，否则返回 false 。

要求空间复杂度 $O(1)\$ ，时间复杂度 $O(logn)\$

示例1

输入

[1],1

输出

true

算法知识视频讲解

Java

输出些什么好

import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @param target int整型 
     * @return bool布尔型
     */
    public boolean search (int[] A, int target) {
        // write code here
        
        if(A == null || A.length <= 0) return false;
        
        int left=0,right = A.length-1;
        
        while(left<=right){
            int mid = (left+right)/2;
            if(A[mid] == target) return true;
            // 如果重复跳过重复再循环一次
            if (A[left] == A[mid]) { 
                left++;
                continue;
            }
            if(A[left] < A[mid]){
                if(A[mid]>target && A[left] <= target){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                if(A[mid] < target && A[right] >= target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            /*if(A[mid]>=A[right]){
                if(A[mid] > target && A[right] <= target){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                if(A[mid] < target && A[left] >= target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }*/
        }
        return false;
    }
}

编辑于 2020-09-11 16:25:00 回复(0)

Java

华科平凡

暴力法：


public class Solution {
    public boolean search(int[] A, int target) {
        for (int num : A)
            if (num == target)
                return true;
        return false;
    }
}

编辑于 2018-07-04 10:23:21 回复(0)

Java

The_Flash

public class Solution {
public boolean search(int[] A, int target) {
//暴力求解
if(A.length == 0)
return false;
for(int i = 0; i < A.length ; i++)
{
if(target == A[i])
return true;
}
return false;
}
}

发表于 2017-12-18 11:29:51 回复(0)

Java

党和人民请赐我一个offer

思想：二分查找

    public boolean search(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;

            if (target == A[mid])
                return true;
            else if (A[lo] == A[mid] && A[mid] == A[hi]) {
                lo++;
                hi--;
            }
            else if (A[lo] <= A[mid]) {
                if (A[lo] <= target && target < A[mid])
                    hi = mid - 1;
                else lo = mid + 1;
            }
            else if (A[mid] <= A[hi]) {
                if (A[mid] < target && target <= A[hi])
                    lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return false;
    }

编辑于 2017-06-02 19:47:02 回复(0)

Java

城市里的养猫者

Since we will have some duplicate elements in this problem, it is a little tricky because sometimes we cannot decide whether to go to the left side or right side. So for this condition, I have to probe both left and right side simultaneously to decide which side we need to find the number. Only in this condition, the time complexity may be O(n). The rest conditions are always O(log n).

For example:

input: 113111111111, Looking for target 3.

Is my solution correct? My code is as followed:

public class Solution { public boolean search(int[] A, int target) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. int i = 0; int j = A.length - 1; while(i <= j){ int mid = (i + j) / 2; if(A[mid] == target) return true; else if(A[mid] < A[i]){ if(target > A[j])
                    j = mid - 1; else if(target < A[mid])
                    j = mid - 1; else i = mid + 1;
            }else if(A[mid] > A[i]){ if(target < A[mid] && target >= A[i])
                    j = mid - 1; else i = mid + 1;
            }else{ // A[mid] == A[i] if(A[mid] != A[j])
                    i = mid + 1; else{ boolean flag = true; for(int k = 1; mid - k >= i && mid + k <= j; k++){ if(A[mid] != A[mid - k]){
                            j = mid - k;
                            flag = false; break;
                        }else if(A[mid] != A[mid + k]){
                            i = mid + k;
                            flag = false; break;
                        }
                    } if(flag) return false;
                }
            }
        } return false;
    }
}

发表于 2017-03-12 11:47:43 回复(0)

Java

詆調壹點

import java.util.*;
public class Solution {
    public boolean search(int[] A, int target) {
		Arrays.sort(A);
		int low = 0;
		int high = A.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if(A[mid] == target) return true;
			else if(A[mid] > target) high = mid - 1;
			else low = mid + 1;
		}
		return false;
	}
}

编辑于 2017-03-24 18:59:14 回复(2)