9

我遇到了一个必须在 O(logn) 中完成的面试问题

给定一个排序的整数数组和一个数字，找到数组中数字的开始和结束索引。

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6} 

Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}

我正在尝试为此找到一个有效的算法，但如此胖并没有成功。

4

6 回答 6

4

您可以使用二进制搜索的概念来查找开始和结束索引：

  • 要找到起始索引，请将数组减半，如果值等于或大于输入 number，则重复数组的下半部分，否则重复上半部分。当你到达一个大小为 1 的数组时停止。
  • 要找到起始索引，请将数组减半，如果值大于输入 number，则重复数组的下半部分，否则重复上半部分。当你到达一个大小为 1 的数组时停止。

请注意，当我们到达一个大小为 1 的数组时，我们可能是输入数字旁边的一个单元格，因此我们检查它是否等于输入数字，如果不等于，我们通过从找到的索引中加/减 1 来修复索引。

findStartIndex(int[] A, int num)
{
    int start = 0; end = A.length-1;

    while (end != start) 
    {
        mid = (end - start)/2;

        if (A[mid] >= num)
            end = mid;
        else
            start = mid;
    }

    if(A[start] == num) 
        return start;
    else 
        return start+1;
}

findEndIndex(int[] A, int num)
{
    int start = 0; end = A.length-1;

    while (end != start) 
    {
        mid = (end - start)/2;

        if (A[mid] > num)
            end = mid;
        else
            start = mid;
    }

    if(A[start] == num) 
        return start;
    else 
        return start-1;
}

以及整个过程：

int start = findStartIndex(A, num);

if (A[start]!=num) 
{ 
     print("-1,-1"); 
}
else
{
     int end = findEndIndex(A, num);
     print(start, end);
}
于 2013-11-07T19:24:45.077 回答
2

听起来像二进制搜索——日志图 iirc 表示每次增量“减半”的效果，这基本上是二进制搜索。

伪代码：

Set number to search for
Get length of array, check if number is at the half point
if the half is > the #, check the half of the bottom half. is <, do the inverse
repeat
    if the half point is the #, mark the first time this happens as a variable storing its index
    then repeat binary searches above , and then binary searches below (separately), such that you check for how far to the left/right it can repeat.
    note*: and you sort binary left/right instead of just incrementally, in case your code is tested in a dataset with like 1,000,000 3's in a row or something

这是否足够清楚，可以从那里开始？

于 2013-11-07T18:41:03.563 回答
2

解决方案是在开始时同时对数组进行二进制搜索（实际上不必是并发的 :P ）。关键是左右搜索略有不同。对于右侧，如果遇到骗子，则必须向右搜索，对于左侧，如果遇到骗子，则必须向左搜索。你正在寻找的是边界，所以在你检查的右侧。 

 yournum, not_yournum

这是边界，在左侧您只需搜索相反方向的边界。最后返回边界的索引。

于 2013-11-07T18:48:31.843 回答
0

双二分查找。您从下索引 = 0，上索引 = 长度 - 1 开始。然后在中途检查点并相应地调整索引。

诀窍是一旦找到目标，枢轴就会分成两个枢轴。

于 2013-11-07T18:42:49.893 回答
0

由于还没有人发布工作代码，我将发布一些（Java）：

public class DuplicateNumberRangeFinder {
    public static void main(String[] args) {
        int[] nums = { 0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9 };
        Range range = findDuplicateNumberRange(nums, 3);

        System.out.println(range);
    }

    public static Range findDuplicateNumberRange(int[] nums, int toFind) {
        Range notFound = new Range(-1, -1);

        if (nums == null || nums.length == 0) {
            return notFound;
        }

        int startIndex = notFound.startIndex;
        int endIndex = notFound.endIndex;
        int n = nums.length;
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == toFind && (mid == 0 || nums[mid - 1] < toFind)) {
                startIndex = mid;
                break;
            } else if (nums[mid] < toFind) {
                low = mid + 1;
            } else if (nums[mid] >= toFind) {
                high = mid - 1;
            }
        }

        low = 0;
        high = n - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == toFind && (mid == n - 1 || nums[mid + 1] > toFind)) {
                endIndex = mid;
                break;
            } else if (nums[mid] <= toFind) {
                low = mid + 1;
            } else if (nums[mid] > toFind) {
                high = mid - 1;
            }
        }

        return new Range(startIndex, endIndex);
    }

    private static class Range {
        int startIndex;
        int endIndex;

        public Range(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public String toString() {
            return "[" + this.startIndex + ", " + this.endIndex + "]";
        }
    }
}
于 2014-11-07T05:38:22.303 回答
0

这可能是我的错误，但是当我测试它时，Ron Teller 的答案有一个无限循环。这是 Java 中的一个工作示例，如果您将函数更改为不是静态的，则可以在此处进行测试。searchRange

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class RangeInArray {
    // DO NOT MODIFY THE LIST
    public static ArrayList<Integer> searchRange(final List<Integer> a, int b) {
        ArrayList<Integer> range = new ArrayList<>();

        int startIndex = findStartIndex(a, b);

        if(a.get(startIndex) != b) {
            range.add(-1);
            range.add(-1);
            return range;
        }

        range.add(startIndex);
        range.add(findEndIndex(a, b));
        return range;
    }

    public static int findStartIndex(List<Integer> a, int b) {
        int midIndex = 0, lowerBound = 0, upperBound = a.size() - 1;

        while(lowerBound < upperBound) {
            midIndex = (upperBound + lowerBound) / 2;
            if(b <= a.get(midIndex)) upperBound = midIndex - 1;
            else lowerBound = midIndex + 1;
        }

        if(a.get(lowerBound) == b) return lowerBound;
        return lowerBound + 1;
    }

    public static int findEndIndex(List<Integer> a, int b) {
        int midIndex = 0, lowerBound = 0, upperBound = a.size() - 1;

        while(lowerBound < upperBound) {
            midIndex = (upperBound + lowerBound) / 2;
            if(b < a.get(midIndex)) upperBound = midIndex - 1;
            else lowerBound = midIndex + 1;
        }

        if(a.get(lowerBound) == b) return lowerBound;
        return lowerBound - 1;
    }

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(2);
        list.add(2);
        list.add(2);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(4);
        list.add(4);
        list.add(4);
        list.add(5);
        list.add(5);
        list.add(5);
        System.out.println("Calling search range");
        for(int n : searchRange(list, 2)) {
            System.out.print(n + " ");
        }
    }
}
于 2018-03-08T13:48:41.513 回答