剑指offer--数组中出现次数超过一半的数字(java)

悠悠 2021-11-01 07:34 281阅读 0赞

### 剑指offer--数组中出现次数超过一半的数字 ###

两种常见解法：

1.  首先排序，超过一半的那个数字一定在中间，但是**注意**通过遍历判断是否存在这样超过半数的数字，不能盲目就指定就是中间那个数字；  
    **时间复杂度：O(nlogn)**
    
        public int MoreThanHalfNum_Solution(int [] array) { 
            	if(array== null || array.length == 0){ 
            		return 0;
            	}
            	quick_sort_new(array);//对数组进行排序，这里是用的快排
            	int arrLen = array.length;
            	int count = 0;
            	for(int i=0;i<arrLen;i++) { 
            		if(array[i]==array[arrLen/2])
            			count++;
            	}
            	if(count>arrLen/2)
            		return array[array.length/2];
            	else { 
        			return 0;
        		}        
            }
            //以下是快排实现
        	private void quick_sort_new(int[] array) { 
        		sort_new(array, 0 ,array.length-1);		
        	}
        
        	private void sort_new(int[] array, int low, int high) { 
        		if(low<high) { 
        			int index = getSplitIndex(array, low, high);
        			sort_new(array, low, index-1);
        			sort_new(array, index+1, high);
        		}
        	}
        
        	private int getSplitIndex(int[] array, int low, int high) { 
        		int SplitValue = array[low];
        		int lowIndex = low;
        		while(low<high) { 
        			while(low<high && array[high]>SplitValue)
        				high--;
        			while(low<high && array[low]<= SplitValue)
        				low++;
        			if(low<high) { 
        				int temp = array[low];
        				array[low] = array[high];
        				array[high] = temp;
        			}
        		}
        		array[lowIndex] = array[low];
        		array[low] = SplitValue;
        		return low;
        	}

2.一列数中，如果某个数字个数超过半数，同时删除两个不一样的数字，那么这个数字的个数依然超过半数。  
所以使用两个变量：一个是存放结果-result，一个用于计数-count  
遍历数组，如果count==0，那么result存当前数，继续遍历下一个数；  
当遇到的当前数与result相同，那么count++；否则count–；  
这样不断抵消两个不一样的数字，最终result中存放的就是个数超半的。  
**时间复杂度：O(n)**

public int MoreThanHalfNum_Solution(int [] array) { 
        	if(array== null || array.length == 0){ 
        		return 0;
        	}
        	int result = array[0];
        	int count = 1;
        	for(int i =1;i<array.length;i++) { 
        		if(count ==0) { 
    				result = array[i];
    				count = 1;
    				continue;
        		}
        		if(array[i]==result) { 
        			count++;
        		}
        		else{ 
    				count--;
    			}
        	}
        	count = 0;
        	for(int i =0;i<array.length;i++) { //遍历判断找到的那个数是否超半数
        		if(array[i] == result)
        			count++;
        	}
        	if(count>array.length/2)
        		return result;
        	return 0;
        }