美文网首页
面试题 08.03. 魔术索引

面试题 08.03. 魔术索引

作者: itbird01 | 来源:发表于2022-01-23 12:45 被阅读0次
    题目.png

    题意:魔术索引。 在数组A[0...n-1]中,有所谓的魔术索引,满足条件A[i] = i。给定一个有序整数数组,编写一种方法找出魔术索引,若有的话,在数组A中找出一个魔术索引,如果没有,则返回-1。若有多个魔术索引,返回索引值最小的一个。

    解法1:
    1.暴力解法,遍历int数组,找到对应的下标

    解法2:
    1.二分查找,按照二分查找的思想,编写代码即可

    解题遇到的问题

    后续需要总结学习的知识点

    ##解法1
    class Solution {
        public int findMagicIndex(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                if (i == nums[i]) {
                    return i;
                }
            }
            return -1;
        }
    }
    
    ##解法2
    class Solution {
        public int findString(String[] words, String s) {
            int res = binarySearch(words, 0, words.length - 1, s);
            return res;
        }
    
        private int binarySearch(String[] words, int i, int j, String s) {
            while (i <= j) {
                int mid = (i + j) / 2;
                if (words[mid].equals("")) {
                    if (words[j].equals(s)) {
                        return j;
                    } else {
                        j--;
                    }
                } else {
                    if (words[mid].equals(s)) {
                        return mid;
                    } else if (words[mid].compareTo(s) > 0) {
                        j = mid - 1;
                    } else {
                        i = mid + 1;
                    }
                }
            }
            return -1;
        }
    }
    

    相关文章

      网友评论

          本文标题:面试题 08.03. 魔术索引

          本文链接:https://www.haomeiwen.com/subject/hhguhrtx.html