Can't do better than linear?


  • 0
    Y

    My solution is linear search. I don't see why you should go for anything fancier, since the problem cannot be solved in less than Ω(n) time anyway. Or at least I think so.

    Why is an asymptotically better solution impossible? Think of an array [3, 3, 3, 3...] and target 4. You cannot make sure that 4 is not in the array, before checking every number in it.

    public class Solution {
        public boolean search(int[] nums, int target) {
            for (int i = 0; i < nums.length; ++i) if (nums[i] == target) return true;
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.