数组元素分类聚合

数组元素分类聚合，譬如给出数组[1 3 1 4 0],找出所有小于k的元素，并通过对换数组的元素，使所有小于k的元素聚集在一起，问最少要调换几次？如本例中，若k=2，则将1和4对换或将0和3对换，都能达到目的，即最少对换一次 思路：找出一个长度等于数组中小于k的元素个数的滑窗，这个滑窗中不小于k的元素个数最少

#华为机试第二题：
import sys
for line in sys.stdin:
    s=line.strip().split()
    sint=list(map(int,s)) #把元素都转成数字
    cnt=0
    k=int(input())
    for i in sint:
        if i<k:
            cnt+=1  #先找出所有小于k的元素个数，即滑窗的长度
    minx=cnt;left=right=tarcnt=0
    while right<len(s):
        if sint[right]>k: #元素从右边进入滑窗，判断新进的元素是否比k大
            tarcnt+=1  
            if (right-left+1)==cnt: #判断滑窗大小是否已经丰满
                minx=min(minx,tarcnt) #只存储较小的值
            left+=1  #滑窗左边界右移
            if sint[left-1]>k: #右移要注意是否把目标元素移出去了
                tarcnt-=1  #若移出去了要及时更新计数器
        right+=1 #滑窗右边界右移
    print(minx) #输出结果

变种，充分利用python的切片及count方法优势

import sys
for line in sys.stdin:
    s=line.strip().split()
    sint=list(map(int,s))
    cnt=0
    k=int(input())
    for i in range(len(sint)):
        if sint[i]<k:
            cnt+=1 #先找出所有小于k的元素个数，即滑窗的长度
        else:
            sint[i]=k+1 #把所有不小于k的元素统一成一个大值方便下面用count方法
    minx=cnt;left=tarcnt=0
    while left<len(s)-cnt: #不用像上面那么麻烦，直接利用切片功能
        tarcnt=(sint[left:left+cnt].count(k+1))#也不用一个个判断，直接用count方法
        minx=min(minx,tarcnt)#只存储较小的值
        left+=1 #窗口右移
    print(minx)