【nowcoder】找出字符串中连续最长的数字串、数组中出现次数超过一半的数字（三种思路解决）

字符串中找出连续最长的数字串

字符串中找出连续最长的数字串

解析：

• i 下标遍历字符串
• 走到 是数字的 字符就拼接到 cur，直到走到第一个不是数字的字符，停止拼接，此时就得到了一个 cur 字符串
• 将 cur 和 ret 对比，如果cur的长度更长，把cur赋给ret；如果cur不如ret长，就把cur重新复制成空字符串""
• 在最后需要考虑字符串尾部是最长数字串的情况，此时i走完了，跳出循环，但是还没有把cur赋给ret，需要再判断一次

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String cur = "";//创建两个空字符串
        String ret = "";
        int i = 0;
        for(; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch >='0' && ch <='9'){
                //当前字符是数字的话 就把字符放入cur中
                cur = cur + ch + ""; //加 "" 变成字符串
            }else{
                //不是数字的话分成两种情况考虑
                if(cur.length() > ret.length()){
                    //当前字符串比上一个大 ，替换
                    ret = cur;
                }else{
                    // cur 不比 ret 长，清空cur
                    cur = "";
                }
            }
        }
        //考虑字符串尾部是最长数字串的情况
        //此时i走完了，跳出循环，但是还没有把cur赋给ret
        if(i == s.length() && cur.length() > ret.length()){
            ret = cur;
        }
        System.out.println(ret);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

数组中出现次数超过一半的数字

数组中出现次数超过一半的数字

解析：

思路一：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。这种方法虽然容易理解，但由于

涉及到快排sort，其时间复杂度为O(NlogN)并非最优

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) {
            return 0;
        } 
        Arrays.sort(array);
        int len = array.length;
        int midNum = array[len/2];
        int count = 0;
        for(int i = 0;i < len;i++) {
            if(array[i] == midNum) {
                count++;
            }
        } 
        if(count > len/2) {
            return midNum;
        } 
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

思路二：先给数组排序，利用map的key value模型来存放arr[i]和相对应出现的次数

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //利用map的key value模型来存放arr[i]和相对应出现的次数
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < array.length ; i++){
            if(map.containsKey(array[i])){
                map.put(array[i],map.get(array[i])+1);
            }else{
                map.put(array[i],1);
            }
        }
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            if(entry.getValue() > array.length/2){
                return entry.getKey();
            }
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路三：抵消法

众数：就是出现次数超过数组长度一半的那个数字

如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length==0) {
            return 0;
        }
        int result = array[0];
        int times = 1; // 次数
        for(int i=1;i<array.length;++i){
            if(times != 0){
                if(array[i] == result) {
                    times++; // 相同则加1
                }else{
                    times--; // 不同则减1
                }
            }else {
            // 更新result的值为当前元素，并置次数为1
                result = array[i];
                times = 1;
            }
        }
        // 判断result是否符合条件，即出现次数大于数组长度的一半
        times = 0; //把times置为0
        for(int i=0;i<array.length;++i){
            if(array[i] == result) ++times;
        } 
        return (times > array.length/2) ? result : 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28