Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Hint: pay attention to the corner cases, line 6 to line 9. If the target is smaller than the first element, just return 0. If the target is greater than the last element, just return the length.

01 public int searchInsert(int[] A, int target) {
02   
03   if(A.length==0) return 0;
04     if(target>A[A.length-1]) return A.length;
05   
06     int start=0, end=A.length-1;
07   
08     while(start<end)
09     {
10         int mid=start+(end-start)/2;
11       
12         //find the target
13         if(A[mid]==target)
14         {
15             return mid;
16         }
17           
18         else if(A[mid]<target)
19         {
20             start=mid+1;
21         }
22       
23         else
24         {
25             end=mid;
26         }
27     }
28     return start;
29 }

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Java语言: Next Permutation

01 public void nextPermutation(int[] num) {
02     int i=num.length-1;
03     while(i>0 && num[i-1]>=num[i])
04     {
05         i--;
06     }
07     reverse(num,i,num.length-1);
08     if(i-1>=0)
09     {
10         int large=binarySearchUpper(num,i,num.length-1,num[i-1]);
11         swap(num, i-1,large);
12     }
13 }
14 
15 public void swap(int[] num, int i, int j)
16 {
17     int temp=num[i];
18     num[i]=num[j];
19     num[j]=temp;
20 }
21 
22 public void reverse(int[]num, int start, int end)
23 {
24     while(start<end)
25     {
26         swap(num, start, end);
27         start++;
28         end--;
29     }
30 }
31 
32 public int binarySearchUpper(int []num, int lo, int hi, int target)
33 {
34     int mid=(lo+hi)/2;
35     while(lo<hi)
36     {
37         if(num[mid]<=target)
38         {
39             lo=mid+1;
40         }
41         else
42         {
43             hi=mid;
44         }
45         mid=(lo+hi)/2;
46     }
47     return mid;
48 }

Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

This question looks very much similar to the merge step of external sorting.

http://en.wikipedia.org/wiki/External_sorting 

The time complexity of this merge takes O(nk) in our process because each time we take O(k) to find the minimum of each pass, and we have n passes. However, if we use a data structure of heap or tournament tree when finding the min element, the complexity can be reduced to O(nlogk).

public class ListNode {
   int val;
   ListNode next;
   ListNode(int x) {
       val = x;
       next = null;
   }
}

Java: MergeKSortedLists

public ListNode mergeKLists(ArrayList<ListNode> lists) {
   if(lists.isEmpty())
       return null;
   ArrayList<ListNode> nodes=new ArrayList<ListNode>();
   for(int i=0;i<lists.size();i++)
   {
       if(lists.get(i)!=null)
           nodes.add(lists.get(i));
   }
 
   if(nodes.isEmpty())
       return null;          
   ListNode min;      
   ListNode head=null;
   ListNode curr=head;
 
   while(!nodes.isEmpty())
   {          
       min=nodes.get(0);
       for(int i=0;i<nodes.size();i++)
       {
           if( nodes.get(i).val<=min.val)
           {                                      
               min=nodes.get(i);
           }
       }
     
       if(head==null)
       {
           head=min;
           curr=head;
       }          
     
       else
       {          
           curr.next=min;
           curr=curr.next;
       }
     
       nodes.remove(min);
       if(min.next!=null)
           nodes.add(min.next);          
   }
 
   return head;
}

Search Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

The key idea is to know that there must be one half side is in normal order. Remember this, then the problem is easy to solve.

Java: SearchRotatedArray

01 public int search(int[] A, int target) {

02     return binarySearch(A,0,A.length-1,target);

03 }

04 

05 public int binarySearch(int []A, int start, int end, int target)

06 {

07     if(start>end)

08         return -1;

09     int mid=start+(end-start)/2;

10     if(A[mid]==target)

11     {

12         return mid;

13     }

14     else

15     {

16         if(A[start]<A[mid]) //first half is in order

17         {

18             if(target>=A[start]&&target<=A[mid]) //target in first half, just search that half

19             {

20                 return binarySearch(A,start,mid-1,target);

21             }

22             else //target in the second half, search it recursively

23             {

24                 return binarySearch(A,mid+1,end,target);

25             }

26         }

27         else if(A[start]>A[mid]) //first half is rotated, then second half is in order

28         {

29             if(target>=A[mid] && target<=A[end]) //target is in the second half

30             {

31                 return binarySearch(A,mid+1,end,target);

32             }

33             else //target is in the first half, search for it recursively

34             {

35                 return binarySearch(A,start,mid-1,target);

36             }

37         }

38         else //A[start]==A[mid], search the second half

39         {

40             return binarySearch(A,mid+1,end,target);

41         }

42         

43     }

44 }

Follow up for "Search in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

If duplicates are allowed, the question becomes more tricky. We need to handle the duplication cases specially. See line 37 -- line 50.

Java: SearchRotatedArrayII

01 public boolean search(int[] A, int target) {
02     return binarySearch(A,0,A.length-1,target);
03 }
04 
05 public boolean binarySearch(int []A, int start, int end, int target)
06 {
07     if(start>end)
08         return false;
09     int mid=start+(end-start)/2;
10     if(A[mid]==target)
11     {
12         return true;
13     }
14   
15     if(A[start]<A[mid])
16     {
17         if(target>=A[start]&&target<=A[mid])
18         {
19             return binarySearch(A,start,mid-1,target);
20         }
21         else
22         {
23             return binarySearch(A,mid+1,end,target);
24         }
25     }
26     else if(A[start]>A[mid])
27     {
28         if(target>=A[mid] && target<=A[end])
29         {
30             return binarySearch(A,mid+1,end,target);
31         }
32         else
33         {
34             return binarySearch(A,start,mid-1,target);
35         }
36     }
37     else if(A[start]==A[mid])
38     {
39         if(A[mid]!=A[end])
40         {
41             return binarySearch(A,mid+1,end,target);
42         }
43         else
44         {                                  
45             boolean result=binarySearch(A,start,mid-1,target);
46             if(result==false)
47                 return binarySearch(A,mid+1,end,target);
48             else
49                 return result;                  
50         }
51       
52     }
53     return false;  
54 }

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

This question looks very much like the binary search problem. But we may have multiple target values, and we need to find the first position and the last position of that. What should we do? An insight just come to mind is that we should find the last number that is smaller than the target, as well as the first number that is greater than the target. They are found by the functions of bsearchlower() and bsearchupper() respectively. We call this pair of indexes "left" and "right". When we find them, we should check whether A[++left] equals the target value. If it is, we then check whether A[--right] equals the target value. and than the left, right will be the index we want to return. Otherwise the target does not exist in the array and we just return [-1,-1].

Java: SearchInARange

01 public int[] searchRange(int[] A, int target) {
02     int[]result=new int[2];
03     int lo=0;
04     int hi=A.length-1;
05     if(A[hi]<target ||A[lo]>target )
06     {
07         result[0]=-1;
08         result[1]=-1;
09         return result;
10     }
11     int left=bsearchlower(A,target,lo,hi);
12     if(A[left]<target)
13         left=left+1;      
14     if(A[left]==target)
15     {
16         result[0]=left;
17         int right=bsearchupper(A,target,lo,hi);
18         if(A[right]>target)      
19             right=right-1;      
20         if(A[right]==target)
21             result[1]=right;        
22         else
23         {
24             result[0]=-1;
25             result[1]=-1;                          
26         }          
27     }
28   
29     else
30     {
31         result[0]=-1;
32         result[1]=-1;                      
33     }      
34     return result;      
35 }
36 
37 //Find the last number that is smaller than target
38 public int bsearchlower(int [] A, int target, int lo, int hi)
39 {
40     if(lo>hi||target<A[lo]||target>A[hi])
41     {
42         return -1;
43     }
44     int mid=(lo+hi+1)/2;
45     while(lo<hi)
46     {
47         if(A[mid]<target)
48         {
49             lo=mid;
50         }
51         else
52         {
53             hi=mid-1;
54         }
55         mid=(lo+hi+1)/2;
56     }
57     return mid;
58 }
59 
60 //Find the first number that is greater than target
61 public int bsearchupper(int[] A, int target, int lo, int hi)
62 {
63     if(lo>hi ||target<A[lo]||target>A[hi])
64     {
65         return -1;
66     }
67     int mid=(lo+hi)/2;
68     while(lo<hi)
69     {
70         if(A[mid]>target)
71         {
72             hi=mid;
73         }
74         else
75         {
76             lo=mid+1;
77         }
78         mid=(lo+hi)/2;
79     }
80     return mid;
81 }