本文按照牛客網(wǎng)的順序神郊，呕滋恚客網(wǎng)劍指offer刷題網(wǎng)址：https://www.nowcoder.com/ta/coding-interviews

本篇涉及的題目有：
1、數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
2姻报、最小的K個(gè)數(shù)
3己英、連續(xù)子數(shù)組的最大和
4、把數(shù)組排成最小的數(shù)
5吴旋、丑數(shù)
6剧辐、數(shù)組中的逆序?qū)?/p>

1寒亥、數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

問題描述
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半邮府，請找出這個(gè)數(shù)字荧关。例如輸入一個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次褂傀，超過數(shù)組長度的一半忍啤，因此輸出2。如果不存在則輸出0同波。

思路解析
假設(shè)有數(shù)字超過數(shù)組長度的一半粟焊，我們使用一個(gè)計(jì)數(shù)器悲雳，如果該數(shù)字出現(xiàn)一次透典，計(jì)數(shù)器加一税弃，如果不是該數(shù)字顽决，計(jì)數(shù)器減一茸时，那么到最后，計(jì)數(shù)器一定是大于0的。那么我們可以按照如下的規(guī)則：我們首先假設(shè)最終的結(jié)果是數(shù)組的第一個(gè)數(shù)，計(jì)數(shù)器初始為1。從第二個(gè)數(shù)開始遍歷，如果與當(dāng)前的數(shù)相同，計(jì)數(shù)器加1行剂，如果不同遂填，判斷計(jì)數(shù)器的狀態(tài)礁击，如果大于0链烈，則減一码荔；如果等于零，則置1域蜗。同時(shí)將假設(shè)的最終結(jié)果變?yōu)楫?dāng)前的數(shù)。
這里最后要判斷最后的結(jié)果是不是真的出現(xiàn)了一半以上的次數(shù)噪猾。

代碼實(shí)現(xiàn)
java

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0)
            return 0;
        int res = array[0];
        int count = 1;
        for(int i=1;i<array.length;i++){
            if(array[i]==res)
                count += 1;
            else if (count==0){
                count = 1;
                res = array[i];
            }
            else
                count -= 1;
        }
        count = 0;
        for(int i=0;i<array.length;i++){
            if(array[i] == res)
                count += 1;
        }
        if(count>array.length / 2)
            return res;
        else
            return 0;
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        res = numbers[0]
        count = 1
        for num in numbers[1:]:
            if num == res:
                count = count + 1
            else:
                if count == 0:
                    res = num
                    count = 1
                else:
                    count = count - 1
        count = 0
        for num in numbers:
            if num == res:
                count = count + 1
        if count > len(numbers) / 2:  
            return res
        else:
            return 0

2、最小的K個(gè)數(shù)

問題描述
輸入n個(gè)整數(shù)筑累，找出其中最小的K個(gè)數(shù)袱蜡。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,慢宗。

思路解析
使用堆排序坪蚁，找到最小的K個(gè)數(shù)晚树。

代碼實(shí)現(xiàn)
java

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arr=new ArrayList<Integer>();
        int len=input.length;
        if(k>len)
            return arr;
        for(int i=0;i<k;i++){
             heapsort(input,i,len);
            arr.add(input[i]);
        }
        return arr;
    }
     
     
    void heapsort(int[] input,int i,int len){
        for(int j=len-1;j>=i;j--){
              int p=(j+i-1)/2;
            if(input[p]>input[j]){
                int temp=input[p];
                input[p]=input[j];
                input[j]=temp;
            }   
        }      
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if len(tinput) < k or k==0:
            return []
        self.buildHeap(tinput[:k],k)
        for i in range(k,len(tinput)):
            if tinput[i] > self.heap[0]:
                continue
            else:
                self.heap[0] = tinput[i]
                self.perceDown(0,k)
        return sorted(self.heap)
        
    def buildHeap(self,tinput,k):
        self.heap = tinput
        for i in range(k//2,-1,-1):
            self.perceDown(i,k)
            
    def perceDown(self,i,k):
        temp = self.heap[i]
        while (2 * i + 1) < k:
            child = 2 * i + 1
            if (child < k - 1) and self.heap[child] < self.heap[child+1]:
                child = child + 1
            if temp < self.heap[child]:
                self.heap[i] = self.heap[child]
                i = child
            else:
                break
        self.heap[i] = temp       

3扇住、連續(xù)子數(shù)組的最大和

問題描述
HZ偶爾會拿些專業(yè)問題來忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問題很好解決威根。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會彌補(bǔ)它呢缅茉？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開始,到第3個(gè)為止)嘴脾。你會不會被他忽悠住蔬墩？(子向量的長度至少是1)

思路解析
這道題跟之前我在網(wǎng)易面試的股票買賣問題類似译打，采用的叫Kadane's Algorithm的方法，用兩個(gè)指針拇颅。maxSum指針記錄此前所有碰到的最大值奏司，curSum指針記錄循環(huán)到當(dāng)前元素這一輪的最大值。當(dāng)循環(huán)到元素i時(shí)樟插，如果i+curSum < i的話韵洋，說明此前的和是負(fù)的，需要舍棄黄锤，所以將curSum的值變?yōu)閕搪缨，反之，將curSum的值變?yōu)閕+curSum猜扮，表明當(dāng)前的和還是正值勉吻，可以繼續(xù)向前探索，由于每一次遍歷一個(gè)元素之后都會比較一下curSum和maxSum旅赢，所以可以放心的繼續(xù)向前遍歷齿桃。

代碼實(shí)現(xiàn)
java

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0)
            return 0;
        int maxCur = array[0];
        int maxSoFar = array[0];
        for(int i = 1;i<array.length;i++){
            maxCur = Math.max(maxCur+array[i],array[i]);
            maxSoFar = Math.max(maxSoFar,maxCur);
        }
        return maxSoFar;
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        maxCur = array[0]
        maxSoFar = array[0]
        for t in array[1:]:
            maxCur = max(t,maxCur + t)
            maxSoFar = max(maxSoFar,maxCur)
        return maxSoFar

4惑惶、把數(shù)組排成最小的數(shù)

問題描述
輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù)短纵，打印能拼接出的所有數(shù)字中最小的一個(gè)带污。例如輸入數(shù)組{3，32香到，321}鱼冀，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。

思路解析
這道題其實(shí)希望我們能夠找到一個(gè)排序規(guī)則悠就，數(shù)組根據(jù)這個(gè)規(guī)則排序之后能排成一個(gè)最小的數(shù)字千绪。要確定排序的規(guī)則，就要比較兩個(gè)數(shù)字梗脾，也就是給出兩個(gè)數(shù)字m和n荸型，我們需要確定一個(gè)規(guī)則判斷m和n哪個(gè)應(yīng)該排在前面，而不是僅僅比較這兩個(gè)數(shù)字的值哪個(gè)更大炸茧。

根據(jù)題目的要求瑞妇，兩個(gè)數(shù)字m和n能拼接稱數(shù)字mn和nm。如果mn<nm梭冠，那么我們應(yīng)該打印出mn辕狰，也就是m應(yīng)該拍在n的前面，我們定義此時(shí)m小于n控漠；反之蔓倍，如果nm<mn，我們定義n小于m润脸。如果mn=nm,m等于n柬脸。

代碼實(shí)現(xiàn)
java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        int n;
        String s="";
        ArrayList<Integer> list=new ArrayList<Integer>();
        n=numbers.length;
         
        for(int i=0;i<n;i++){
            list.add(numbers[i]);//將數(shù)組放入arrayList中
        }
        //實(shí)現(xiàn)了Comparator接口的compare方法，將集合元素按照compare方法的規(guī)則進(jìn)行排序
        Collections.sort(list,new Comparator<Integer>(){
         
            @Override
            public int compare(Integer str1, Integer str2) {
                // TODO Auto-generated method stub         
                    String s1=str1+""+str2;
                    String s2=str2+""+str1;
                     
                    return s1.compareTo(s2);
                }
            });
         
        for(int j:list){
            s+=j;
        }
        return s;
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here]
        if not len(numbers):
            return ""
        arr = [str(x) for x in numbers]
        arr.sort(lambda x,y:cmp(x+y,y+x))
        return int("".join(arr))

5毙驯、丑數(shù)

問題描述
把只包含因子2倒堕、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6爆价、8都是丑數(shù)垦巴，但14不是，因?yàn)樗蜃?铭段。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)骤宣。求按從小到大的順序的第N個(gè)丑數(shù)。

思路解析
暴力求解丑數(shù)是不可行的序愚，使用動(dòng)態(tài)規(guī)劃的解法憔披，首先我們要確保數(shù)組里的已有的丑數(shù)是排好序的，同時(shí)要維護(hù)三個(gè)索引。

代碼實(shí)現(xiàn)
java

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index == 0)
            return 0;
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(1);
        int nextMin=1;
        for(int i=2;i<=index;i++){
            nextMin = Math.min(Math.min(arr.get(index2) * 2,arr.get(index3) * 3),arr.get(index5) * 5);
            arr.add(nextMin);
            if(arr.get(index2) * 2 <= nextMin)
                index2 += 1;
            if(arr.get(index3) * 3 <= nextMin)
                index3 += 1;
            if(arr.get(index5) * 5 <= nextMin)
                index5 += 1;
        }
        return nextMin;
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index<=0:
            return 0
        res = [1]
        index2 = 0
        index3 = 0
        index5 = 0
        while(len(res) < index):
            
            nextMin = min(res[index2] * 2,res[index3] * 3,res[index5] * 5)
            res.append(nextMin)
            while res[index2] * 2 <= nextMin:
                index2 = index2 + 1
            while res[index3] * 3 <= nextMin:
                index3 = index3 + 1
            while res[index5] * 5 <= nextMin:
                index5 = index5 + 1
        return res[-1]

6芬膝、數(shù)組中的逆序?qū)?/h1>

問題描述
在數(shù)組中的兩個(gè)數(shù)字望门，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)γ趟］斎胍粋€(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P筹误。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007

思路解析
使用歸并排序的思路進(jìn)行求解

代碼實(shí)現(xiàn)
java

import java.io.*;
import java.util.*;
public class Main {
    public static int InversePairs(int [] array) {
        if(array==null||array.length==0)
        {
            return 0;
        }
        int[] copy = new int[array.length];
        for(int i=0;i<array.length;i++)
        {
            copy[i] = array[i];
        }
        int count = InversePairsCore(array,copy,0,array.length-1);//數(shù)值過大求余
        return count;
              
    }
    private  static int InversePairsCore(int[] array,int[] copy,int low,int high)
    {
        if(low==high)
        {
            return 0;
        }
        int mid = (low+high)>>1;
        int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
        int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
        int count = 0;
        int i=mid;
        int j=high;
        int locCopy = high;
        while(i>=low&&j>mid)
        {
            if(array[i]>array[j])
            {
                count += j-mid;
                copy[locCopy--] = array[i--];
                if(count>=1000000007)//數(shù)值過大求余
                {
                    count%=1000000007;
                }
            }
            else
            {
                copy[locCopy--] = array[j--];
            }
        }
        for(;i>=low;i--)
        {
            copy[locCopy--]=array[i];
        }
        for(;j>mid;j--)
        {
            copy[locCopy--]=array[j];
        }
        for(int s=low;s<=high;s++)
        {
            array[s] = copy[s];
        }
        return (leftCount+rightCount+count)%1000000007;
    }

python

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        if len(data) > 1:
            mid = len(data) / 2
            left_half = data[:mid]
            right_half = data[mid:]
            left_count = self.InversePairs(left_half)%1000000007
            right_count = self.InversePairs(right_half)%1000000007
            i,j,k,count = len(left_half)-1,len(right_half)-1,len(data)-1,0
            while i >= 0 and j >= 0:
                if left_half[i] < right_half[j]:
                    data[k] = right_half[j]
                    j = j - 1
                    k = k - 1
                else:
                    data[k] = left_half[i]
                    count += (j+1)
                    i = i - 1
                    k = k - 1
            while i >= 0:
                data[k] = left_half[i]
                k = k - 1
                i = i - 1
            while j>=0:
                data[k] = right_half[j]
                k = k - 1
                j = j - 1
            return (count + left_count + right_count)%1000000007
        else:
            return 0