Java日记2018-05-18

第一题 数组中的逆序对
使用归并排序

第二题 两个链表的第一个公共结点

image.png

如上所示对于一个链表a+b+c=b+c+a,使用两个指针指向A B两个链表的头，同时向下走，走到最后时，a指针从链表A尾端放到B链表头端，b指针从B尾端放A头端，继续往下直到指针指向的两者相等

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode l1 = pHead1, l2 = pHead2;
    while (l1 != l2) {
        l1 = (l1 == null) ? pHead2 : l1.next;
        l2 = (l2 == null) ? pHead1 : l2.next;
    }
    return l1;
}

第三题 数字在排序数组中出现的次数
排序数组就二分查找，找到第一个索引，以及最后一个索引，相减就是最后结果

public class GetNumberOfK {
    public static int getnum(int[] arr, int k) {
        int number = 0;
        if (arr.length > 0) {
            int first = getFirstK(arr, k, 0, arr.length - 1);
            int last = getLastK(arr, k, 0, arr.length - 1);
            if (first > -1 && last > -1)
                number = last - first + 1;
        }
        return number;
    }

    private static int getFirstK(int[] arr, int k, int left, int right) {
        if (left > right)
            return -1;
        int mid = (left + right) / 2;
        System.out.println("mid:"+mid);
        if (arr[mid] == k) {
            if ((mid > 0 && arr[mid - 1] != k) || mid == 0) {
                return mid;
            } else {
                right = mid - 1;
            }
        } else if (arr[mid] > k) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }

        return getFirstK(arr, k, left, right);
    }

    private static int getLastK(int[] arr, int k, int left, int right) {
        if (left > right)
            return -1;
        
        int mid = (left + right) / 2;
        System.out.println("mid:"+mid+" right："+right+" left:"+left);
        if (arr[mid] == k) {
            if (mid < arr.length - 1 && arr[mid + 1] != k ||( mid == arr.length - 1)) {
                return mid;
            } else {
                left = mid + 1;
            }
        } else if (arr[mid] < k) {
            left = mid + 1;

        } else {
            right = mid - 1;
        }

        return getLastK(arr, k, left, right);

    }

}